归并排序是一种基于分治法的排序算法。为了排序长度为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）。
