众所周知，归并排序（mergesort）就是以分治的思想，把输入数列分为几段，递归的把这几段排好，然后再通过归并（merge）操作把这几段拼起来，从而将整个数列排序。典型的归并就是2路归并排序。
归并排序的时间复杂度是O(nlogn)的，但它的一个显著问题就是需要额外的存储空间来辅助排序，空间复杂度是O(n)的，与quicksort和heapsort相比就逊色了不少。能否让它的空间复杂度为O(1)呢，即不使用辅助空间来进行merge排序？答案当然是yes。事实上，1969年的时候M. A. Kronrod就已经解决了这个问题。也正因为这样，Knuth在TAOCP里面出这道40分的练习题的时候把他的名字也写在旁边了（见TAOCP第168页）。这个问题虽然很早就已经解决了，但是仍然在被研究，最新的结果还是去年得到的。对这个问题学者们主要关注已不是复杂度的问题而是具体的运算次数，目标是让比较操作和交换操作的次数尽可能的少（是不是很钻牛角尖？）。
好了，背景介绍完了，该说说我想讨论的问题了。在这里我想讨论一下O(1)空间复杂度的merge排序的意义。所能想到的意义有两个：
一是把这个算法用到嵌入式设备上。
因为嵌入式设备一般内存很小，通过算法来节省内存是一个比较好的做法，但问题也就来了，把辅助空间降到O(1)，随之而来的代价是计算上的复杂，比较次数和交换次数的增加，相应的使设备耗电更多。问题是省电的意义大还是省内存的意义大呢？
二是把这个算法用到外部排序上。
初看这样的算法确实可以提高外部排序的效率，但是具体如何做呢？一般两路的外部排序是从源文件里读出内存大小的一块，然后在内存中排序，在放回文件里，这样生成若干文件。然后在从其中两个文件中读数据，按照merge的方式写到另一个文件中去。这一步根本用不到辅助空间。唯一可能用到辅助空间的地方是前面的一步，即将一块数据在内存中排序。但问题是，这一步完全可以用heapsort一类的O(1)空间复杂度的排序算法完成，因此这里用mergesort并不是必要的。那么O(1)空间的mergesort意义又何在呢？
