C++ STL中的近百个算法，绝大多数都是非常简单，用10行程序足以说明。但是，inplace_merge这个算法，却是相当地复杂，伤脑啊。

如果有线性额外空间，合并仅需要O(n)时间；如果是堆排序，原地执行，时间复杂度是O(n log n)。

=============================

In-place Merge Sort (原地归并排序)

转贴自：  http://hi.baidu.com/jakisou/item/f7b8d2d558db35fecb0c3911 略微加以润色与评论

一般在提到Merge Sort时，大家都很自然地想到Divide-and-Conqure, O(n lgn)的时间复杂度以及额外的O(n)空间。O(n)的extra space似乎成了Merge Sort最明显的缺点，但实际上这一点是完全可以克服的，也就是说，我们完全可以实现O(n lgn) time 以及 O(1) space 的Merge Sort。对于这种不用额外空间(即常数大小的额外空间)的算法，有一个通用的名字叫做In-place Algorithms，因此我们称该归并算法为in-place merge sort，也就是原地归并排序。

在进入具体的细节之前，先来看一个稍后会用到的引论 ：

给定长度分别为n和m的两个各自有序数组X，Y，以及一个长度为n的辅助数组A，存在O(m+n)时间复杂度的算法AuxSort;该算法可以原地归并排序X和Y，同时A中元素保持不变(顺序可能打乱)。

看到留言说用了辅助数组A，空间复杂度就是O(n)了。所以先提前在这解释下：AuxSort算法中确实用到了长度为n的辅助数组A。但是在最终的算法 中，AuxSort会作为subroutine，而我们会将待排序数组的一部分作为这个辅助数组A，而不是另外开辟一块空间。所以最终的空间复杂度仍然是 O(1)。所以请大家耐心往下看。。。

AuxSort算法具体步骤如下：

1. 交换X 和 A。

2. 维护两个整数下标 px, py，初始化为0，分别代表A[0]和Y[0]; 另外维护一个dest指针，初始化指向X[0]，并且该指针在移动到X[n-1]后，自动过渡到Y[0]。

3. 比较A[px], Y[py]：
   若 A[px] <= Y[py],   swap(A[px++], *dest++); 
   若 A[px]  >  Y[py]，swap(Y[py++], *dest++);

4. 若A中仍有剩余元素，则将剩余部分依次与*dest交换。当然每一步要执行dest++操作。【Y中有剩余元素不必再操作了，此时已经保持有序】

通 过上述步骤很容易发现，该算法的基本思想与传统的2-way merge sort如出一辙，时间复杂度也都是O(m+n)。只不过传统的 merge sort中我们要申请额外的目的数组存储排序完成后的数据; 而这里目的数组就是X+Y本身，所以我们要首先交换X和A，将X “腾空”【反复思考，如果没有这么一段额外存储空间，那么保持线性时间复杂度就难了】；另 外传统的merge sort中是将X或Y中的数据赋值给新开辟的目的数组Z，但是这里我们的目的数组中数据不能被破坏，因此只能采用swap操作。

为了有助于理解，我们来看一个例子。假设n=3，且x1 < y1 < x2 < y2< x3 < y3，AuxSort具体的执行过程如图1所示。

http://s9/mw690/001x63y2gy6FyoVQQTm28&690Merge 原地归并 【转贴】" TITLE="In-place Merge 原地归并 【转贴】" />

图1 利用辅助数组原地归并排序

下面开始本文的重点，in-place merge sort算法，具体内容参考自TAOCP Vol3 5.2.5 习题，根据Knuth的记述，

Knuth, Donald (1998). "Section 5.2.4: Sorting by Merging". Sorting and Searching. The Art of Computer Programming 3 (2nd ed.). Addison-Wesley. pp. 158–168. ISBN 0-201-89685-0.

该算法出自

Kronrod, M.A. An optimal ordering algorithm without a field of operation (in Russian), Dok. Aknd. Nauk SSSR 186 (1969), 1256-1258.  Soviet Mathematics - Doklady 10. p. 744.

如果感觉抓不住一篇论文的精髓，那么看看后来的引用文献对这篇被引论文的总结：block rearrangement、internal buffering、employ O(sqrt(n)) blocks each of size O(sqrt(n)). this approach allows the user to employ one block as an internal buffer to aid in rearranging or otherwise manipulating the other blocks in constant extra space. Since only the contents of the buffer and the relative order of the blocks need ever be out of sequence, linear time is sufficient to sort both the buffer and the blocks (each sort involves O(sqrt(n)) keys) and thereby complete the merge. 

这帮人真是神人。。。废话不说了，直接进入到正题吧。

假设我们有两个已经各自有序的数组X和Y，其总长度为N，如图2所示。下面将要介绍的算法将利用O(1)的额外空间，在O(N)的时间内将其原地排序。总体来说算法分为3部分：分块，两两归并，扫尾。

http://s10/mw690/001x63y2gy6Fyp06gtP29&690Merge 原地归并 【转贴】" TITLE="In-place Merge 原地归并 【转贴】" />

图2 原始数组

分块：我们将原始数组组合在一起，并以长度n=sqrt(N)将其分成m+2份： Z1, Z2, … Zm+1, Zm+2，如图3所示。【平方根确保了降低到lg N这个数量级。由于n^2<=N<=(n+1)^2，所以m<=n】这样，除了Zm+2中有(N % n)个元素之外，其他m+1块都恰好有n个元素。

http://s8/mw690/001x63y2gy6Fyp4UZBt67&690Merge 原地归并 【转贴】" TITLE="In-place Merge 原地归并 【转贴】" />

图3 分块

另 外，如图3所示，假设X[-1] (X中的最后一个元素)包含在Zk中，那么我们将其与Zm+1交换。这样一来，Z1, Z2, …, Zm 中的元素都 各自有序，且规模为n。我们将调整之后的Zm+1和Zm+2统称为A，其规模s为[n, 2n)。【A视为无序】如上两步在O(N)时间内即可完成。

两两归并： 根据每一块中的第一个元素大小调整Z1, Z2, ... Zm的顺序，使得Z1[0] <= Z2[0] <= … <= Zm[0]。若第一个元素相等，则以最后一个元素的大小作为依据。由于无法利用额外空间，我们可以采用选择排序：每一轮从剩余的块里面选择一个 首元素最小的块，与当前块交换。最坏情况下进行m轮，每一轮需要O(m)的比较, O(n)的交换，总体的时间复杂度为O(m(m+n))=O(N)。【m与n都是sqrt(N) 】

如 此排列好之后，我们便可以从Z1和Z2开始进行两两归并排序。由于A的长度s>=n，这里我们可以采用前文介绍的AuxSort方法。唯一的缺点是 A中的元素顺序会被打乱，但由于A中元素本来也就无序，所以也就无所谓了。也就是说，我们要执行m-1轮AuxSort算法，其中第i轮处理Zi和 Zi+1。通过下面的归纳法证明，我们可以得知，这m-1轮AuxSort过程执行完之后，Z1~Zm中所有的元素就已经排序完毕了。

在此之前首先假设排序结束之后的第i块为Ri，而经过AuxSort处理后的Zi为Z’i。另外，为了描述方便，我们把Z1~Zm中属于X的第一块叫做X1，属于Y的第一块叫做Y1，依次类推。

我们接下来将要证明——在第i轮处理后，Ri = Z’i 【即第i轮处理后得到的Z'i即为最终结果的Ri】；以及，在第i轮处理后，Z'i+1为剩下的所有元素中经过“分块”处理后应该放在最头部的，这样对剩下的所有元素可以重新重头施加原地归并操作。

1. i=1。不失一般性，我们假设Z1为X1，那么Z1, Z2, Z3 可能为{X1, X2, X3},  {X1, X2, Y1},  {X1, Y1, X2}, {X1, Y1, Y2}. 往证R1 = Z’1且Z’2[0] <= Z3[0] ：

   1.1 {X1, X2, X3}。 则X1[n-1] <= X2[0] = Z2[0] <= Zi[0] <= Zi[k] (i>=2)，也就是说，X1包含 最小的n个元素，R1 = X1=Z’1。另外，Z’2[0] = Z2[0] = X2[0] <= Zi[0] (i>=3)。

   1.2 {X1, X2, Y3}。同上，X1[n-1] <= Z2[0] <= Zi[k] (i>=2)，因此R1=X1=Z’1。另外，Z’2[0]=Z2[0]<=Zi[0] (i>=3)。

   1.3 {X1, Y1, X2}。显然最小的n个元素一定在X1或Y1中，因此R1=Z’1。另外，Z’2[0] <= max(X1[n-1], Y1[0]) <= X2[0] = Z3[0]。

   1.4 {X1, Y1, Y2}。同理，最小的n个元素一定在X1或Y1中，R1=Z’1。另外，Z’2[0] <= Y1[n-1] <= Y2[0] = Z3[0]

   因 此merge之后, Z’2[0] <= Z3[0]的性质仍然成立。在随后的分析中，如果Z’2[n-1] = X1[n-1],  那么可以将 Z’2看成是X1; 同理如果Z’2[n-1] = Y1[n-1]，我们可以将其看成是Y1。这是一个很重要的推论，直接支持我们在随后继续沿用上述四 种情况的分析。

2. 假设i=k的时候结论成立，也就是说k轮AuxSort之后，R1~Rk已经就位。且根据上一步中的推论，Z’k+1可以直接看作是Xi或Yj。也就是说，上一步中四种分情况讨论的方法依旧适用。证毕;

3. 综上所述，根据归纳法我们可以得知结论成立。

由于共经过m-1轮两两归并，每一轮归并时间复杂度为O(2n)，因此第二步总体时间复杂度为O(mn) = O(N)。

扫尾：“两两归并”步结束之后，R[0...m*n-1]已经排序完毕。由于A中共有s个元素，容易看出，原始数组中最大的s个元素一定存在于A和R[m*n-s, m*n- 1]中。因此我们可以利用选择排序，在O(s^2) = O(N)时间内将A和R[m*n-s, m*n-1]排序，这样最大的s个元素就被移动到A中。换句 话说，R[0, m*n-1]中存储着原始数组中的前N-s个元素。

利 用AuxSort, 可以以A为辅助数组，将R[0...m*n-s-1] (长度为N-2s)和 R[m*n-s, m*n-1] (长度为s) 归并排序。 这样原始数组中的前N-s个元素排序完毕，时间复杂度为O(N)。由于A中元素顺序已经被打乱，我们需要再次利用选择排序在O(s^2)=O(N)的时间 内对其重新排序。

这样一来，通过分块，两两归并，以及扫尾三个步骤以后，我们完成了对于X和Y的一轮原地归并排序，时间复杂度为O(N)，空间复杂度为O(1)。以此为基础，完整的归并排序可以在O(NlogN)时间内完成，空间复杂度仍然为O(1)。

注意由于AuxSort基于交换操作，A中元素的顺序会被打乱，因此该排序算法是不稳定的。

后记：

记 不得最开始听说这个概念是什么时候了，最近有印象的一次是去年去STC面试，面试官问到merge sort的时候说这个有什么缺点啊？我说好像也没啥特 别的缺点，普遍认为的O(n)的extra space可以省掉，因为我们有in-place merge sort。面试官于是很感兴趣地让我描述一下 大致流程。:( 可怜我当时其实并不知道具体的步骤，大囧了一把。好在面试官也没有计较 

后 来回去之后翻STL中的inplace_merge研究了一下，发现这个并不是纯正的in-place merge sort，也有可能会用到额外的 buffer，非常失望，就没有继续研究了。前段时间又一次心血来潮，发现这原来是TAOCP里面的一道习题，于是结合答案终于搞定之。由于Knuth的答案一向简单明了，其中关于两两归并这一步正确性的证明我没太看明白，只好自己重新推导了一遍，因此写起来要比原文罗嗦许多。没有时间的同学，也许回头直接看原文会好很多。:D

另外，stable in-place merge sort也是TAOCP的习题之一 (所以说TAOCP看得慢并不能说明我笨啊。。。)，等我有时间的时候，再继续整理吧~ 希望不会拖太久哈哈。

========================

Bing-Chao Huang, Michael A. Langston: Practical In-Place Merging. Commun. ACM 31(3): 348-352 (1988)

全文： http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.1155&rep=rep1&type=pdf