归并排序java实现

public class MergeSort {
//基本思想为分治法，将有序的子序列合并，得到有序的序列。先使每个子序列有序，再使子序列段间有序。
//当有 n 个记录时，需进行 logn 轮归并排序，每一轮归并比较次数不超过 n，元素移动次数为 n，因此时间复杂度为 O(nlogn)。
//归并排序时需要和待排序记录个数相等的存储空间，所以空间复杂度为 O(n)。适用于数据量大，并且对稳定性有要求的情况。
    private static void mergeSort(int[] arr, int l, int mid, int r) {// 将arr[l~mid]和arr[mid+1~r]两部分进行归并
    //合并两个已排序的数组，取两个输入数组 A 、 B，一个输出数组 C，三个计数器 i、j、k，初始化为对应数组的开始端。
    //A[i] 和 B[j] 中较小者拷贝到 C 中的下一个位置，相关计数器前进一次。当两个输入数组有一个用完时候，则将另外一个数组中剩余部分拷贝到 C 中。
        int[] aux = Arrays.copyOfRange(arr, l, r + 1);//拷贝
        int i = l, j = mid + 1;// 初始化，i指向左半的起始索引l；j指向右半起始索引mid+1
        for (int k = l; k ) {
            if (i > mid) {  // 左半元素处理完毕
                arr[k] = aux[j - l];
                j++;
            } else if (j > r) {   // 右半元素处理完毕
                arr[k] = aux[i - l];
                i++;
            } else if (aux[i - l].compareTo(aux[j - l]) // 左半所指元素 
                arr[k] = aux[i - l];
                i++;
            } else {  // 左半所指元素 >= 右半所指元素
                arr[k] = aux[j - l];
                j++;
            }
        }
    }

    private static void sort(int[] arr, int i, int j) {// 递归使用归并排序,对arr[l~r]的范围进行排序
        if (i >= j)//参数错误
            return;
        int mid = (i + j) / 2;
        sort(arr, i, mid);
        sort(arr, mid + 1, j);    
        if (arr[mid].compareTo(arr[mid + 1]) > 0)// 只mergeSort arr[mid] > arr[mid+1]的情况
            mergeSort(arr, i, mid, j);
    }

    public static void main(String[] args) {
    int[] arr = new int[]{10, 0, 5, 8, -1,-8, 10, 0};
        System.out.print("排序前数组：")
        for (int n :arr) 
            System.out.print(n + ",");
        sort(arr,0,arr.length-1);
    System.out.print("排序后数组：")
        for (int n :arr) 
            System.out.print(n + ",");
    }
}