归并排序

一、概念及其介绍

归并排序（Merge sort）是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法(Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

二、适用说明

当有 n 个记录时，需进行 logn 轮归并排序，每一轮归并，其比较次数不超过 n，元素移动次数都是 n，因此，归并排序的时间复杂度为 O(nlogn)。归并排序时需要和待排序记录个数相等的存储空间，所以空间复杂度为 O(n)。

归并排序适用于数据量大，并且对稳定性有要求的场景。

class Solution {
    public int[] sortArray(int[] nums) {
        int[] result = new int[nums.length];
        sort(nums, 0, nums.length-1, result);
        return result;
    }

    public void sort(int [] nums, int l, int r, int [] result) {
        if(l>=r) {
            return;
        }
        int mid = (l + r) / 2;
        sort(nums, l, mid, result);
        sort(nums, mid + 1, r, result);
        merge(nums, l, r, mid, result);
    }

    public void merge(int [] nums, int l, int r, int mid, int [] result) {
        int i = l;
        int j = mid + 1;
        int k;
        for(k = l;k<= r;k++) {
            if(i>mid) {
                result[k] = nums[j];
                j++;
            } else if(j>r) {
                result[k] = nums[i];
                i++;
            } else if(nums[i] < nums[j]) {
                result[k] = nums[i];
                i++;
            } else {
                result[k] = nums[j];
                j++;
            }
        }
        for(int p = l; p<= r; p++) {
            nums[p] = result[p];
        }
    }
}

注意最后：

for(int p = l; p<= r; p++) {
            nums[p] = result[p];
        }

需要将排序后的拷贝到原数组中，这样才能满足后面的递归合并的是两个已经排好序的数组。

参考：https://www.runoob.com/data-structures/merge-sort.html