Knuth将此作为练习(Vol 3, 5.2.5)。确实存在就地归并排序。它们必须谨慎执行。

首先，这里描述的简单的就地合并并不是正确的解决方案。它将性能降低到O(N2)。

其思想是对数组的一部分进行排序，而将其余部分用作合并的工作区域。

例如下面的合并函数。

void wmerge(Key* xs, int i, int m, int j, int n, int w) {
    while (i < m && j < n)
        swap(xs, w++, xs[i] < xs[j] ? i++ : j++);
    while (i < m)
        swap(xs, w++, i++);
    while (j < n)
        swap(xs, w++, j++);
}  

取数组xs，两个排序的子数组分别表示为范围[i, m)和[j, n)。工作区域从w开始，与大多数教科书给出的标准合并算法相比，该算法在排序子数组和工作区域之间交换内容。结果，前一个工作区域包含合并的排序元素，而存储在工作区域中的前一个元素被移动到两个子数组中。

但是，有两个约束条件是必须满足的:

工作区域应该在数组的边界内。换句话说，它应该足够大，以容纳交换进来的元素，而不会引起任何越界错误。 工作区域可以与两个排序数组中的任何一个重叠;但是，它必须确保没有任何未合并的元素被覆盖。

定义了这个合并算法后，很容易想象出一个解决方案，它可以对数组的一半进行排序;接下来的问题是，如何处理剩余的未排序部分存储在工作区域，如下图所示:

... unsorted 1/2 array ... | ... sorted 1/2 array ...

一个直观的想法是对工作区域的另一半进行递归排序，这样就只有1/4的元素还没有排序。

... unsorted 1/4 array ... | sorted 1/4 array B | sorted 1/2 array A ...

这一阶段的关键点是我们必须归并已排序的1/4元素B 对1/2个元素A进行排序。

剩下的工作区域(只包含1/4个元素)是否大到足以合并 A和B?不幸的是，事实并非如此。

然而，上面提到的第二个约束给了我们一个提示，如果我们能确保合并序列中未合并的元素不会被覆盖，我们可以通过安排工作区域与任何一个子数组重叠来利用它。

实际上，我们不需要对工作区域的后半部分进行排序，而是可以对前半部分进行排序，并将工作区域放在两个排序数组之间，就像这样:

... sorted 1/4 array B | unsorted work area | ... sorted 1/2 array A ...

这种设置有效地安排了工作区域与子阵列a的重叠 在Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola中提出。“实用的就地归并排序”。计算机学报，1996]。

所以剩下的唯一事情就是重复上面的步骤，这将工作区域从1/2,1/4,1/8，…当工作区域变得足够小(例如，只剩下两个元素)，我们可以切换到普通的插入排序来结束这个算法。

下面是基于本文在ANSI C语言中的实现。

void imsort(Key* xs, int l, int u);

void swap(Key* xs, int i, int j) {
    Key tmp = xs[i]; xs[i] = xs[j]; xs[j] = tmp;
}

/* 
 * sort xs[l, u), and put result to working area w. 
 * constraint, len(w) == u - l
 */
void wsort(Key* xs, int l, int u, int w) {
    int m;
    if (u - l > 1) {
        m = l + (u - l) / 2;
        imsort(xs, l, m);
        imsort(xs, m, u);
        wmerge(xs, l, m, m, u, w);
    }
    else
        while (l < u)
            swap(xs, l++, w++);
}

void imsort(Key* xs, int l, int u) {
    int m, n, w;
    if (u - l > 1) {
        m = l + (u - l) / 2;
        w = l + u - m;
        wsort(xs, l, m, w); /* the last half contains sorted elements */
        while (w - l > 2) {
            n = w;
            w = l + (n - l + 1) / 2;
            wsort(xs, w, n, l);  /* the first half of the previous working area contains sorted elements */
            wmerge(xs, l, l + n - w, n, u, w);
        }
        for (n = w; n > l; --n) /*switch to insertion sort*/
            for (m = n; m < u && xs[m] < xs[m-1]; ++m)
                swap(xs, m, m - 1);
    }
}

其中wmerge是前面定义的。

完整的源代码可以在这里找到，详细的解释可以在这里找到

顺便说一下，这个版本并不是最快的归并排序，因为它需要更多的交换操作。根据我的测试，它比标准版本更快，标准版本在每次递归中分配额外的空间。但它比优化版本慢，优化版本提前将原始数组翻倍，并将其用于进一步合并。

这是我的C版本:

void mergesort(int *a, int len) {
  int temp, listsize, xsize;

  for (listsize = 1; listsize <= len; listsize*=2) {
    for (int i = 0, j = listsize; (j+listsize) <= len; i += (listsize*2), j += (listsize*2)) {
      merge(& a[i], listsize, listsize);
    }
  }

  listsize /= 2;

  xsize = len % listsize;
  if (xsize > 1)
    mergesort(& a[len-xsize], xsize);

  merge(a, listsize, xsize);
}

void merge(int *a, int sizei, int sizej) {
  int temp;
  int ii = 0;
  int ji = sizei;
  int flength = sizei+sizej;

  for (int f = 0; f < (flength-1); f++) {
    if (sizei == 0 || sizej == 0)
      break;

    if (a[ii] < a[ji]) {
      ii++;
      sizei--;
    }
    else {
      temp = a[ji];

      for (int z = (ji-1); z >= ii; z--)
        a[z+1] = a[z];  
      ii++;

      a[f] = temp;

      ji++;
      sizej--;
    }
  }
}

它确实不容易或不有效，我建议您不要这样做，除非您真的必须这样做(您可能不必这样做，除非这是家庭作业，因为就地合并的应用程序主要是理论性的)。你不能用快速排序代替吗?无论如何，通过一些简单的优化，快速排序都会更快，而且它额外的内存是O(log N)。

不管怎样，如果你一定要做，那就必须做。这是我的发现:一和二。我不熟悉就地归并排序，但它的基本思想似乎是使用旋转来方便合并两个数组，而不使用额外的内存。

注意，这甚至比传统的归并排序还要慢。

包括它的“大结果”，本文描述了就地归并排序的几个变体(PDF):

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf

少移动的就地排序

于尔基·卡塔贾宁、托米·

证明了n 元素可以使用O(1)进行排序 额外空间，O(n log n / log log n) 元素移动，nlog2n + O(nlog Log n)比较。这是第一次 需要就地排序算法 O (nlogn)在最坏情况下移动 同时保证O(n log n) 比较，不过由于不变 所涉及的因素是算法 主要是理论兴趣。

我认为这也是相关的。我有一份打印本，是同事传给我的，但我还没读过。它似乎涵盖了基本理论，但我对这个主题不够熟悉，无法判断它有多全面:

http://comjnl.oxfordjournals.org/cgi/content/abstract/38/8/681

最优稳定合并

安东尼奥斯·西姆沃尼斯

本文介绍了如何稳定地进行归并 两个序列A和B，大小为m和 n, m≤n，分别为O(m+n) 作业,O (mlog (n / m + 1)) 比较和只使用一个常数 额外空间的数量。这 结果匹配所有已知的下界…

利用c++ std::inplace_merge，就地归并排序可以实现如下:

template< class _Type >
inline void merge_sort_inplace(_Type* src, size_t l, size_t r)
{
    if (r <= l) return;

    size_t m = l + ( r - l ) / 2;             // computes the average without overflow

    merge_sort_inplace(src, l,     m);
    merge_sort_inplace(src, m + 1, r);

    std::inplace_merge(src + l, src + m + 1, src + r + 1);
}

更多的排序算法，包括并行实现，可以在https://github.com/DragonSpit/ParallelAlgorithms repo中找到，它是开源的，是免费的。

关键的一步是让合并本身就位。这并不像那些来源说的那么难，但当你尝试的时候，你会失去一些东西。

看看合并的一个步骤:

[…list-sorted…| x列表…| y…发行b…]

我们知道这个排序的序列比其他的都小，x比A中的其他所有的都小，y也比b中的其他所有的都小。在x小于等于y的情况下，你只需要把指针移到A的起始点上。在y小于x的情况下，你必须将y洗牌过整个A来排序。最后一步是代价高昂的原因(退化情况除外)。

它通常更便宜(特别是当数组每个元素实际上只包含单个单词时，例如，一个指向字符串或结构的指针)，用一些空间换取时间，并使用一个单独的临时数组来来回排序。