归并排序

归并排序是一种基于分治法的排序算法。为了排序长度为n的数组，需要先排序两个长度为n/2的子数组，然后合并这两个排序的子数组，于是整个数组也就排序完毕。

归并排序可以用迭代代码实现。例如，输入一个长度为8的数组[4，1，5，6，2，7，8，3]，可以先合并相邻的长度为1的子数组得到4个排序的长度为2的子数组，如图（a）所示。图中的箭头表示源数据位于上面的数组中，合并时将数字写入下面的数组中。然后合并相邻的长度为2的子数组得到2个排序的长度为4的子数组，如图（b）所示。此时源数据位于下面的数组中，合并时将数字写入上面的数组中。最后合并相邻的长度为4的子数组，此时整个数组排序完毕，如图（c）所示。

说明：

（a）合并相邻的长度为1的子数组得到排序的长度为2的子数组；
（b）合并相邻的长度为2的子数组得到排序的长度为4的子数组；
（c）合并相邻的长度为4的子数组得到排序的长度为8的数组

归并排序需要创建一个和输入数组大小相同的数组，用来保存合并两个排序子数组的结果。数组src用来存放合并之前的数字，数组dst用来保存合并之后的数字。每次在完成合并所有长度为n的子数组之后开始新一轮合并长度为2n的子数组之前，交换两个数组。
上述过程可以用如下所示的参考代码实现：

public int[] sortArray (int[] nums) {
    int length = nums.length;
    int[] src = nums;
    int[] dst = new int[length];
    for (int seg = 1; seg < length; seg += seg) {
        for (int start = 0; start < length; start += seg * 2) {
            int mid = Math.min(start + seg, length) ;
            int end = Math.min(start + seg * 2, length) ;
            int i = start, j = mid, k = start;
            while ( i < mid || j < end) {
                if (j == end || (i < mid && src[i] < src[j])) {
                    dst[k++] = src[i++];
                } else {
                    dst[k++] = src[j++]:
                }
            }
        }
        int[] temp = src;
        src = dst;
        dst = temp;
    }
    return src;
}

假设某一时刻准备合并数组src中从下标start开始的两个长度为seg的子数组，第1个子数组的起始下标是start，结束下标是start+seg-1；第2个子数组的起始下标是start+seg，结束下标是start+seg*2-1。变量i、j是分别指向数组src中两个子数组的下标，它们从左到右扫描两个子数组，变量k是指向数组dst的下标。每次从数组src的两个子数组中选择将较小的数字写入数组dst中，最终数组dst中下标从start到start+seg*2-1的子数组就是排序的。
归并排序也可以用递归的代码实现。为了排序长度为n的数组，只需要排序两个长度为n/2的子数组，然后合并两个排序的子数组即可。排序长度为n/2的子数组和排序长度为n的数组是同一个问题，可以递归调用同一个函数解决。归并排序的递归代码如下所示：

public int[] sortArray (int[] nums) {
    int[] dst = new int[nums.length];
    dst = Arrays.copyOf (nums, nums.length);
    mergeSort (nums, dst, 0, nums.length) ;
    return dst;
}

private void mergesort (int[] src, int[] dst, int start, int end) {
    if (start + 1 >= end) {
        return;
    }
    int mid = (start + end) / 2:
    mergeSort (dst, src, start, mid);
    mergeSort(dst, src, mid, end);
    
    int i = start, j = mid, k = start;
    while (i < mid || j < end) {
        if (j == end || (i < mid && src[i] < src[j])) {
            dst[k++] = src[i++];
        } else {
            dst[k++] = src[j++];
        }
    }
}

由于长度为n的数组每次都被分为两个长度为n/2的数组，因此不管输入什么样的数组，归并排序的时间复杂度都是O（nlogn）。归并排序需要创建一个长度为n的辅助数组。如果用递归实现归并排序，那么递归的调用栈需要O（logn）的空间。因此，归并排序的空间复杂度是O（n）。

摘自《剑指Offer（专项突破版）：数据结构与算法名企面试题精讲》