归并排序

方法一：

private static void MergeSort(int[] array, int start, int end){
        if(start>=end)return;
        int mid = (start+end)/2;
        MergeSort(array, start, mid);
        MergeSort(array, mid+1, end);
        MergeOne(array, start, mid, end);
}
private static void MergeOne(int[] array, int start, int mid, int end) {
    int[] temp = new int[end-start+1];
    int k=0,i=start,j=mid+1;
    while(i<=mid && j<= end) {
        //如果前面的元素小于后面的不能构成逆序对
        if(array[i] <= array[j]) {
            temp[k++] = array[i++];
        } else {  //如果前面的元素大于后面的，那么在前面元素之后的元素都能和后面的元素构成逆序对
            temp[k++] = array[j++];
        }
    }
    while(i <= mid)
        temp[k++] = array[i++];
    while( j<= end)
        temp[k++] = array[j++];

    for(int l=0; l<k; l++) {
        array[start+l] = temp[l];
    }
}

public static void main(String[] args) {
    int[] array = new int[]{1, 100, 45, 98, 8, 30, 30, 66, 2, 100, 1};
    MergeSort(array, 0, array.length - 1);
    for (int i : array) {
        System.out.println(i);
    }
}

方法二：

public static void main(String[] args) {
        int[] array = new int[]{1, 100, 45, 98, 8, 30, 30, 66, 2, 100, 1};
        int[] temp = new int[array.length];
        MergeSort(array, 0, array.length - 1, temp);
        for (int i : array) {
            System.out.println(i);
        }
    }

private static void MergeSort(int[] nums, int left, int right, int[] temp) {
        // 切分到只剩下一个数了，逆序对数为0
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        // 对左边子数组nums[left, mid]进行排序
        MergeSort(nums, left, mid, temp);
        // 对右边子数组nums[mid+1, right]进行排序
        MergeSort(nums, mid + 1, right, temp);
        // 将nums[left, mid], nums[mid+1, right]这两个有序子数组合并为一个整体有序的数组nums[left, right]
        merge(nums, left, mid, right, temp);

}

// 借助temp数组，将nums[left, mid], nums[mid+1, right]这两个有序子数组合并为一个整体有序的数组nums[left, right]
private static void merge(int[] nums, int left, int mid, int right, int[] temp) {
    for (int i = left; i <= right; i++) {
        temp[i] = nums[i];
    }

    int l = left; // 指向左边子数组nums[left, mid]的第一个值
    int r = mid + 1; // 指向右边子数组nums[mid+1, right]的第一个值

    for (int j = left; j <= right; j++) {
        if (l < mid + 1 && r < right + 1 && temp[l] <= temp[r]) { // 注意：这里是<=
            nums[j] = temp[l];
            l++;
        } else if (l < mid + 1 && r < right + 1 && temp[l] > temp[r]) {
            nums[j] = temp[r];
            r++;
        } else if (l == mid + 1) { // 左边子数组已经走完了
            // 把右边子数组剩下的都到nums[left, right]中
            nums[j] = temp[r];
            r++;
        } else if (r == right + 1) { // 右边子数组走完了
            // 把右边子数组剩下的都到nums[left, right]中
            nums[j] = temp[l];
            l++;
        }
    }
}