什么是归并排序

归并，就是合并的意思。通俗的说就是把两部分合并成一部分。

归并排序的步骤

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

具体步骤如下：

1、将给定的序列，从中间分成两个子序列，然后再将子序列以同样的方式拆分子序列，直到子序列长度为1，也就是称为有序序列。

2、申请额外的空间，为两个子序列长度和，用于存放合并后的序列。然后设定两个指针分别指向两个有序子序列的起始位置，然后比较两个指针指向元素的大小，将较小的元素放入合并空间，并移动指向该元素的指针，另外一个子序列的指针不变，然后继续比较两个指针指向元素的大小，直到两个有序子序列中的值全部放入合并空间中。

3、自下而上的合并所有的子序列，直到合并完所有的子序列之后，合并空间中的序列即为有序序列。

以图为例：

假设给定的初始序列如下所示：

首先，将给定的无序序列二分，结果如下：

然后自下而上的，合并每两个子序列，过程如图所示：

第一次比较：

以第一组为例，两个子序列分别为[4]和[5]，设定两个指针分别指向这两个有序序列的起始位置，然后进行比较，4<5，所以将较小的4先放入合并空间里，然后移动该序列的指针，因为已经到末尾了，所以，直接把另外一个序列的元素挨个追加到合并空间，即将5追加到合并空间后边。

然后，继续归并：

仍然以第一组为例，两个有序子序列分别为[4,5]和[2,8]，设定两个指针分别指向4和2，2<4，所以先把2放入合并空间，移动指针指向8，4<8，再把4放入合并空间，移动指针，指向5，5<8，再把5放入合并空间，指针已经到达末尾，所以，将8追加到合并空间，完成归并。

最后一次归并结果如下：

至此，归并完毕。

代码实现

public class MergeSort {
 
	public static int[] mergeSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return arr;
		}
		// 找出当前序列的中间位置
		int middle = (int)Math.floor(arr.length / 2);
		// 将序列分隔成两部分
		int[] left = Arrays.copyOfRange(arr, 0, middle);
		int[] right = Arrays.copyOfRange(arr, middle, arr.length);
		// 合并两部分序列，拆分序列，直到每一部分只剩下一个元素，然后合并。递归
		return merge(mergeSort(left), mergeSort(right));
	}
 
	private static int[] merge(int[] left, int[] right) {
		int[] result = new int[left.length + right.length];
		int i = 0;
		while (left.length > 0 && right.length > 0) {
			if (left[0] <= right[0]) {
				result[i++] = left[0];
				left = Arrays.copyOfRange(left, 1, left.length);
			} else {
				result[i++] = right[0];
				right = Arrays.copyOfRange(right, 1, right.length);
			}
		}
		while (left.length > 0) {
			result[i++] = left[0];
			left = Arrays.copyOfRange(left, 1, left.length);
		}
		while (right.length > 0) {
			result[i++] = right[0];
			right = Arrays.copyOfRange(right, 1, right.length);
		}
		return result;
	}
}

复杂度分析

因为归并排序的性能不受初始数据的影响，不管初始数据是否已经排序或者完全倒序，归并排序的时间复杂度都是O(nlogn)，比选择排序性能要好，但是代价是需要额外的空间。