归并排序(Java实现)

归并排序是一种高级排序算法，适用于外部排序，时间复杂度为O(nlogn)，但是由于必须引入辅助数组，空间复杂度为O(n)

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = new int[9999999];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random()*arr.length);
        }
        long start = System.currentTimeMillis();
        mergeSort(arr);
        long end = System.currentTimeMillis();
        System.out.println("归并排序耗时：" + (end - start) + "ms");
    }

    public static void mergeSort(int[] arr){
        int[] tmpArr = new int[arr.length]; //辅助数组
        mergeSort(arr, tmpArr, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int[] tmpArr, int left, int right){
        if (left < right){
            int center = (left + right) / 2; //第一段数组的末尾元素下标
            mergeSort(arr, tmpArr, left, center);
            mergeSort(arr, tmpArr, center + 1, right);
            merge(arr, tmpArr, left, center, right);
        }
    }
    //归并
    private static void merge(int[] arr, int[] tmpArr, int left, int center, int right){
        int rightBegin = center + 1; //第二段数组的起始元素下标
        int tmpIndex = left; //临时数组对应第一段数组的起始元素下标
        int num = right - left + 1; //子数组的长度

        while (left <= center && rightBegin <= right){
            if (arr[left] <= arr[rightBegin])
                tmpArr[tmpIndex++] = arr[left++];
            else
                tmpArr[tmpIndex++] = arr[rightBegin++];
        }

        while (left <= center)
            tmpArr[tmpIndex++] = arr[left++];
        while (rightBegin <= right)
            tmpArr[tmpIndex++] = arr[rightBegin++];

        //tmpArr传给arr
        for (int i = 0; i < num; i++){
            //从右往左插入是因为left已经是center，而right没变
            arr[right] = tmpArr[right];
            --right;
        }

    }
}

归并排序对于海量数据的排序速度比我们之前测试过的希尔排序和堆排序都要快