「数组」归并排序 / if语句优化|小区间插入优化（C++）

概述

在上一篇文章中，我们介绍了快速排序以及随机快速排序：

「数组」快速排序 / 随机值优化|小区间插入优化（C++）

今天，我们来介绍归并排序。

相比于快速排序是冒泡排序融合了分治思想后形成的究极promax进化版，归并排序不来自任何一种使用分治的基础排序：它本人就是纯粹的分治。

思路

冯·诺依曼想过这么一个事：两个有序数组二路合并成一个有序数组的时间复杂度是线性的：

     i  0 1 2 3 4
arr1[i] 1 5 6 8 9
arr2[i] 0 2 3 4 7ans[i] 1 2 3 4 5 6 7 8 9

很明显， 你只需要双指针i和j分别指向两个数组，k指针指向答案数组，

每次都进行ans[k++]=min(arr1[i],arr2[j])，之后i++或j++（这要看min函数取到了谁）

就能在线性时间内得到合并好的数组。

那如果能把一个无序数组在中间一分为二成两个有序的子数组然后合并就好了，但是子数组怎么能有序呢？

那如果能把这两个子数组分成四个有序子数组然后合并就好了。

那如果能把这四个子数组分成八个有序子数组然后合并就好了。

.....................

那如果能把这一个数分成，诶，等等，一个数本来就有序啊。

那从这里再一层一层合并上去不就好了？冯·诺依曼恍然大悟。

算法过程

来把我们的思路实现一遍。

merge_sort()

我们给出函数merge_sort，它接收一个范围，它只干两件事： 

①申请一个辅助数组。

②启动这个层层划分的过程。

让我们谈谈辅助数组:

在二路归并时，我们需要一个地方承载我们的结果。那不如就让原数组承载我们的结果，辅助数组[l,r)位置上拷贝一份原数组[l,r)位置上的值,两个指针i和j都指向辅助数组的对应位置，然后向原数组填入对应的结果。这样我们的排序结果就还放在原来的内存地址上。

void merge_sort(int arr[], int l, int r) {int* assist= new int[r-l];recursion(arr, l, r, assist);delete[] assist;
}

---

recursion()

我们给出递归函数recursion，它只干两件事： 

①一刀劈开接收到的数组，然后传给两个子recursion。

②在劈开的两个数组有序后启动二路合并。

*注意*：根据代码语言传统，l和r往往是一个左闭右开区间，即[l,r），表示范围取到l，但取不到r。两个子数组的范围分别是[l,m),[m,r)。

void recursion(int arr[], int l, int r, int assist[]) {if (r - l <= 1)return;int m = (l + r) / 2;recursion(arr, l, m, assist);recursion(arr, m, r, assist);merge(arr, l, m, r, assist);
}

---

merge() 

我们给出递归函数recursion，它只干两件事： 

①把原数组对应位置的数据拷贝给辅助数组的对应位置。

②进行一个极其简单的二路合并。

*注意*：i或j触底后将另一个数组的剩余部分通通接入合并后数组的末尾。

void merge(int arr[], int l, int m, int r, int assist[]) {memcpy(&assist[l], &arr[l], sizeof(int) * (r - l));int i, j, k;for (i = l, j = m, k = l;; k++) {if (i == m || j == r)break;if (assist[i] <= assist[j])arr[k] = assist[i++];else arr[k] = assist[j++];}while (i != m)arr[k++] = assist[i++];while (j != r)arr[k++] = assist[j++];
}

Code

void merge(int arr[], int l, int m, int r, int assist[]) {memcpy(&assist[l], &arr[l], sizeof(int) * (r - l));int i, j, k;for (i = l, j = m, k = l;; k++) {if (i == m || j == r)break;if (assist[i] <= assist[j])arr[k] = assist[i++];else arr[k] = assist[j++];}while (i != m)arr[k++] = assist[i++];while (j != r)arr[k++] = assist[j++];
}
void recursion(int arr[], int l, int r, int assist[]) {if (r - l <= 1)return;int m = (l + r) / 2;recursion(arr, l, m, assist);recursion(arr, m, r, assist);merge(arr, l, m, r, assist);
}
void merge_sort(int arr[], int l, int r) {int* assist= new int[r-l];recursion(arr, l, r, assist);delete[] assist;
}

谈谈奇数

常有人对于归并排序对于奇数长度数组的可行性产生质疑。我们来思考一下这个问题。

先想想二路归并：

     i  0 1 2 3 4
arr1[i] 1 5 6 8
arr2[i] 0 2 3 4 7ans[i] 1 2 3 4 5 6 7 8

结合上面的merge()实现代码，你能发现：两个长度不同的子数组丝毫不影响二路归并的进行。

那么奇数数组导致的中间位置不均匀丝毫不会影响整个排序。

优化方案

1.if语句优化

在一些时候，二路合并根本没必要发生：第一个有序子数组的最后一个数比第二个有序子数组的第一个数小，那么他们天然就接在了一起。

void merge_if(int arr[], int l, int m, int r, int assist[]) {if (arr[m - 1] <= arr[m])return;memcpy(&assist[l], &arr[l], sizeof(int) * (r - l));int i, j, k;for (i = l, j = m, k = l;; k++) {if (i == m || j == r)break;if (assist[i] <= assist[j])arr[k] = assist[i++];else arr[k] = assist[j++];}while (i != m)arr[k++] = assist[i++];while (j != r)arr[k++] = assist[j++];
}

2.小区间插入优化

最底层会产生大量recursion递归来对小区间二分，而他们分区的范围却极小，这是不必要的，而且相当被动。

插入排序在小区间的表现要好于快速分区，当分区小到某个程度时，我们直接转发给插入排序。

void recursion_with_insertion(int arr[], int l, int r, int assist[]) {if (r - l <= 20){insertion_sort(&arr[l], r - l); return;}int m = (l + r) / 2;recursion_with_insertion(arr, l, m, assist);recursion_with_insertion(arr, m, r, assist);merge_if(arr, l, m, r, assist);
}

Code

void merge_if(int arr[], int l, int m, int r, int assist[]) {if (arr[m - 1] <= arr[m])return;memcpy(&assist[l], &arr[l], sizeof(int) * (r - l));int i, j, k;for (i = l, j = m, k = l;; k++) {if (i == m || j == r)break;if (assist[i] <= assist[j])arr[k] = assist[i++];else arr[k] = assist[j++];}while (i != m)arr[k++] = assist[i++];while (j != r)arr[k++] = assist[j++];
}
void recursion_with_insertion(int arr[], int l, int r, int assist[]) {if (r - l <= 20){insertion_sort(&arr[l], r - l); return;}int m = (l + r) / 2;recursion_with_insertion(arr, l, m, assist);recursion_with_insertion(arr, m, r, assist);merge_if(arr, l, m, r, assist);
}
void MGsort(int arr[], int l, int r) {int* assist = new int[r - l];recursion(arr, l, r, assist);delete[] assist;
}

复杂度

时间复杂度：O(nlogn)

空间复杂度：O(n)

复杂度分析：

时间分析：

把一个长度为n的数组一直二分成长度为1的数组的次数是logn次，也就是有logn层

--------------------------------------
----------------- --------------------
--------- ------- ------ -------------
--- ----- --- --  -- --- --- ---------
- - - --- - - --  -- - - - - ---- ----
- - - - - - - - - - - - - - - - - - --
——————————————————n———————————————————
—m——m——m——m——m——m——m——m——m——m——m——m——m

每一层都要对子数组两两二路合并，复杂度为O(m)，m为子数组的长度 ，而每一层的全体m求和为n，故每一层的复杂度都为O(n)，有logn层，故得到O(nlogn)。

---

空间分析：

使用了长度为n的辅助数组，故为O(n)。

*注意*：同一层的每次合并函数和递归函数结束后空间都会被释放，下次函数都会再次占据这块空间，空间复用使得每一层的复杂度都是O(1)，函数的空间占用整体为O(logn) 。O(n+logn)=O(n)。

总结

分而治之，是为分治。

如果你的朋友问什么是分治，那么就给他讲讲归并排序。作为应用分治思想的算法，它真的纯粹到毫无保留。