---

前言

将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的，所以在合并的时候是很快的。

---

一、递归的方式

通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 …… 直到全部小的数组合并起来。

为方便理解我还准备了动图：

二、代码

public class MergeSort {// 归并排序public static int[] mergeSort(int[] arr, int left, int right) {// 如果 left == right，表示数组只有一个元素，则不用递归排序if (left < right) {// 把大的数组分隔成两个数组int mid = (left + right) / 2;// 对左半部分进行排序arr = mergeSort(arr, left, mid);// 对右半部分进行排序arr = mergeSort(arr, mid + 1, right);//进行合并merge(arr, left, mid, right);}return arr;}// 合并函数，把两个有序的数组合并起来// arr[left..mif]表示一个数组，arr[mid+1 .. right]表示一个数组private static void merge(int[] arr, int left, int mid, int right) {//先用一个临时数组把他们合并汇总起来int[] a = new int[right - left + 1];int i = left;int j = mid + 1;int k = 0;while (i <= mid && j <= right) {if (arr[i] < arr[j]) {a[k++] = arr[i++];} else {a[k++] = arr[j++];}}while(i <= mid) a[k++] = arr[i++];while(j <= right) a[k++] = arr[j++];// 把临时数组复制到原数组for (i = 0; i < k; i++) {arr[left++] = a[i];}}
}

---

然而面试官要你写个非递归式的归并排序怎么办？别怕，我这还撸了个非递归式的归并排序，代码如下：

public class MergeSort {// 非递归式的归并排序public static int[] mergeSort(int[] arr) {int n = arr.length;// 子数组的大小分别为1，2，4，8...// 刚开始合并的数组大小是1，接着是2，接着4....for (int i = 1; i < n; i += i) {//进行数组进行划分int left = 0;int mid = left + i - 1;int right = mid + i;//进行合并，对数组大小为 i 的数组进行两两合并while (right < n) {// 合并函数和递归式的合并函数一样merge(arr, left, mid, right);left = right + 1;mid = left + i - 1;right = mid + i;}// 还有一些被遗漏的数组没合并，千万别忘了// 因为不可能每个字数组的大小都刚好为 iif (left < n && mid < n) {merge(arr, left, mid, n - 1);}}return arr;}
}

总结

性质：
1、时间复杂度：O(nlogn)
2、空间复杂度：O(n)
3、稳定排序
4、非原地排序