1、归并排序的基本思想
以下面的这个数组为例，首先我们将数组对半分割，直到分割成单个元素，此时对于每一个单个元素来说都是有序的，因为就他一个元素嘛，然后开始向上逐渐归并的过程，直到上升到最后一个层级，此时排序结束。
那我们为什么费那么大劲，要将数组先分割在归并呢？大家可以看到我们是对一个长度为“8”的数组进行的排序，一步步通过二分法到单个元素总共是经历了“3”个层级，这个“3”是怎么来的呢？数组长度8/2/2/2=1，8到1总共是经历了3次除以2的操作，也就是log2(8)=3，如果有N个元素，那么就有log2(N)的层级，由此我们可以推断归并排序的时间复杂度是Nlog(N)级别的。
2、归并的过程
可以发现我们要使用递归的方式来逐渐归并，这里以倒数第二层归并到最后一层的过程为例来说明归并的过程。
1、开辟出一个相同的数组空间；
2、设立三个索引，第一个蓝色箭头放在原数组的第一位，第二个红色箭头放在要比较的第一个数组的第一位，第三个红色箭头放在要比较的第二个数组的第一位；
3、比较两个红色箭头索引处元素的大小，将较小的那个元素放到蓝色箭头索引位置处，蓝色箭头索引+1，移动的红色索引+1，然后继续下一轮的比较。
三个索引分别对应：左边的红色箭头定义为i，右边的红色箭头定义为j，上面的蓝色箭头定义为k.
具体代码实现如下：
public class MergeSort {
//第一步：我们对传递的数组从位置0到n-1进行归并排序，因为我们的定义是前闭后闭，当然你也可以使用前闭后开的定义。
public static void mergeSort(int arr[],int n){
mergeSortT(arr, 0, n-1);
}
//第二步：递归归并
public static void mergeSortT(int arr[],int l,int r){
if (l >= r) {
return;
}
int mid = (l+r)/2;
mergeSortT(arr,l,mid);
mergeSortT(arr, mid+1, r);
merge(arr, l, mid,r);
}
//第三步：归并操作
// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
private static void merge(int[] arr, int l, int mid, int r) {
//1、开辟临时数组（因为是闭区间所以这里临时数组的大小为：r-l+1）
int temp[] = new int[r-l+1];
for (int i = l; i <= r; i++) { //注意是L,不是1
temp[i-l] = arr[i];
}
//2、定义索引：i=L,j,k
int i = l,j = mid +1;
for (int k = l; k <= r; k++) { //K=L...
//判断索引越界
if (i>mid) {
arr[k] = temp[j-l];
j++;
}
else if (j>r) {
arr[k] = temp[i-l];
i++;
}
//比较临时数组两边的大小
else if (temp[i-l] <temp[j-l]) {
arr[k] = temp[i-l];
i++;
}
else {
arr[k] = temp[j-l];
j++;
}
}
}
}
测试用例：
public static void main(String[] args) {
Random rand = new Random();
int arr[] = new int[50000];
for (int i = 0; i < 50000; i++) {
int randNum = rand.nextInt() + 1;
arr[i] = randNum;
}
long currentTimeMillis = System.currentTimeMillis();
mergeSort(arr,50000);
long currentTimeMillis2 = System.currentTimeMillis();
System.out.println("基础归并排序所用时间："+(currentTimeMillis2-currentTimeMillis));
}
输出结果：
基础归并排序所用时间：24
3、归并排序的优化
第一步优化：
当我们使用一个近乎有序的数组作为测试用例时候，会发现插入排序的效率比归并排序的效率要高很多！
public static void main(String[] args) {
int[] arr = SortTestHelper.generateNearlyOrderdArray(50000, 10);
int[] copyIntArray = SortTestHelper.copyIntArray(arr, 50000);
long currentTimeMillis = System.currentTimeMillis();
mergeSort(arr,50000);
long currentTimeMillis2 = System.currentTimeMillis();
System.out.println("基础归并排序所用时间："+(currentTimeMillis2-currentTimeMillis));
long currentTimeMillis3 = System.currentTimeMillis();
InsertSort.insertSort(copyIntArray, 0, 50000);
long currentTimeMillis4 = System.currentTimeMillis();
System.out.println("插入排序所用时间："+(currentTimeMillis4-currentTimeMillis3));
}
输出结果：
基础归并排序所用时间：33
插入排序所用时间：4
现在只是对五万个数进行排序，如果测试的数据量更大的话，差距可想而知。这是因为插入排序对于一个近乎有序的数组会降低到O（N）的级别，那么归并排序是否有什么方案对这种特殊的情况进行优化呢？答案是肯定的！
大家来看这一段代码：
public static void mergeSortT(int arr[],int l,int r){
if (l >= r) {
return;
}
int mid = (l+r)/2;
mergeSortT(arr,l,mid);
mergeSortT(arr, mid+1, r);
merge(arr, l, mid,r);
}
在这里我们mergeSortT(arr,l,mid);mergeSortT(arr, mid+1, r);对两个部分进行排序之后不管他们之间的顺序如何，都会进行一次merge操作，是不是有时候可以省略掉这一次merge操作呢？答案是没问题的，当arr[mid] > arr[mid +1]我们才需要merge操作。下面我们将这句话加入到原来的代码中，运行一下：
基础归并排序所用时间：8
插入排序所用时间：4
可见这一步优化对于一个基本有序的数组来说是非常有效的！但是归并排序还是比插入排序要慢一些，这是因为归并排序无法退化成一个O（N）级别的算法。
第二步优化
现在我们的递归是递归到只有一个元素的时候然后return，但是事实上当我们递归到元素量非常小的时候，我们可以转而使用插入排序来提高性能。这是基于两个方面，一方面当我们的元素数量比较小的时候，整个数组近乎有序的概率就会比较大，此时插入排序有优势，另外一方面虽然插入排序的最差事件复杂度是N² 级别的，但是要注意不管是N²还是NlogN都是
有一个N常数的，换句话说当N小到一定程度的时候，插入排序要比归并排序要快一些。为此对于上面的代码我们就可以这样修改：
public static void mergeSortT(int arr[],int l,int r){
/*if (l >= r) {
return;
}*/
if (r-l <=15) {
InsertSort.insertSort(arr, l, r);
return;
}
int mid = (l+r)/2;
mergeSortT(arr,l,mid);
mergeSortT(arr, mid+1, r);
if (arr[mid] > arr[mid+1])
merge(arr, l, mid,r);
}
输出结果：
基础归并排序所用时间：7
插入排序所用时间：3
至此我们的两个优化方案也就完成了~
当然优化是没有止境的，这里就简单介绍这么多，剩下的还需要自己去探索了。
本文用到的一个工具类：
public class SortTestHelper {
public static int[] generateRandomArray(int n, int range_l, int range_r) {
int arr[] = new int[n];
Random rand = new Random();
for (int i = 0; i < n; i++) {
int randNum = rand.nextInt(range_r - range_l + 1) + range_l;
arr[i] = randNum;
}
return arr;
}
public static int[] generateRandomArray(int n) {
int arr[] = new int[n];
Random rand = new Random();
for (int i = 0; i < n; i++) {
int randNum = rand.nextInt();
arr[i] = randNum;
}
return arr;
}
public static int[] generateNearlyOrderdArray(int n, int swapTimes) {
int arr[] = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = i;
}
Random random = new Random();
for (int i = 0; i < swapTimes; i++) {
int posx = random.nextInt(n);
int posy = random.nextInt(n);
int temp = posx;
posx = posy;
posy = temp;
}
return arr;
}
public static int[] copyIntArray(int a[], int n) {
int arr[] = new int[n];
for (int i = 0; i < a.length; i++) {
arr[i] = a[i];
}
return arr;
}
}
