Java实现归并排序

public class MergeSort {
    //将有二个有序数列a[first...mid]和a[mid...last]合并。 
    static void mergearray(int a[], int first, int mid, int last, int temp[]) {
        int i = first, j = mid + 1;
        int m = mid, n = last;
        int k = 0;


        while (i <= m && j <= n) {
            if (a[i] <= a[j])
                temp[k++] = a[i++];
            else
                temp[k++] = a[j++];
        }


        //如果从mid到last的数据已经遍历完毕，将first到mid剩余的数据拷贝至sorted
        while (i <= m) {
            temp[k++] = a[i++];
        }


        //如果从first到mid的数据已经遍历完毕，将mid到last剩余的数据拷贝至sorted
        while (j <= n) {
            temp[k++] = a[j++];
        }


        //至此，temp[]为有序的数组


        //更改a[]中first至last元素顺序，使其排序
        for (i = 0; i < k; i++) {
            a[first + i] = temp[i];
        }
    }


    static void mergesort(int a[], int first, int last, int temp[]) {
        if (first < last) {
            int mid = (first + last) / 2;
            mergesort(a, first, mid, temp); //递归，将数组切割至最小（1个元素）
            mergesort(a, mid + 1, last, temp); //同上
            mergearray(a, first, mid, last, temp); //再将相邻的二个元素合并、排序，往上递归，直至最后合并成一个最大的有序数组 
        }
    }


    public static void main(String[] args) {
        int[] x = { 6, 2, 4, 1, 5, 9, 3 };
        int[] sorted = new int[x.length];
        mergesort(x, 0, x.length - 1, sorted);


        for (int i = 0; i < sorted.length; i++) {
            System.out.println(sorted[i]);
        }
    }
}