利用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中找到，它是开源的，是免费的。

这个答案有一个代码示例，实现了黄炳超和Michael a . Langston在论文《Practical in - place merge》中描述的算法。我不得不承认我不了解细节，但给定的合并步骤的复杂性是O(n)。

从实际的角度来看，有证据表明，纯就地实现在现实场景中并没有表现得更好。例如，c++标准定义了std::inplace_merge，顾名思义，这是一个就地合并操作。

假设c++库通常都得到了很好的优化，看看它是如何实现的是很有趣的:

1) libstdc++ (GCC代码库的一部分):std::inplace_merge

实现委托给__inplace_merge，通过尝试分配一个临时缓冲区来避免这个问题:

typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
_TmpBuf __buf(__first, __len1 + __len2);

if (__buf.begin() == 0)
  std::__merge_without_buffer
    (__first, __middle, __last, __len1, __len2, __comp);
else
  std::__merge_adaptive
   (__first, __middle, __last, __len1, __len2, __buf.begin(),
     _DistanceType(__buf.size()), __comp);

否则，它将退回到一个实现(__merge_without_buffer)，该实现不需要额外的内存，但不再在O(n)时间内运行。

2) libc++ (Clang代码库的一部分):std::inplace_merge

看起来相似。它委托给一个函数，该函数也尝试分配一个缓冲区。它将根据是否获得了足够的元素来选择实现。常量内存回退函数称为__buffered_inplace_merge。

也许回退仍然是O(n)时间，但关键是如果有临时内存可用，他们就不使用实现。

注意，c++标准通过将所需的复杂度从O(n)降低到O(nlog n)，显式地给予实现选择这种方法的自由:

复杂性: 如果有足够的额外内存可用，则正好是N-1个比较。如果内存不足，则比较O(N log N)次。

当然，这并不能证明常数空间在O(n)时间内的合并永远不应该被使用。另一方面，如果它会更快，优化的c++库可能会切换到那种类型的实现。

这是我的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--;
    }
  }
}

I just tried in place merge algorithm for merge sort in JAVA by using the insertion sort algorithm, using following steps. 1) Two sorted arrays are available. 2) Compare the first values of each array; and place the smallest value into the first array. 3) Place the larger value into the second array by using insertion sort (traverse from left to right). 4) Then again compare the second value of first array and first value of second array, and do the same. But when swapping happens there is some clue on skip comparing the further items, but just swapping required.

我在这里做了一些优化;在插入排序中保持较小的比较。我发现这个解决方案的唯一缺点是它需要在第二个数组中更大的数组元素交换。

e.g)

First___Array: 3,7,8,9

第二组:1,2,4,5

然后7,8,9使第二个数组交换(向左移动一个)它的所有元素，每次将自己放在最后一个数组中。

所以这里的假设是交换物品与比较两个物品相比可以忽略不计。

https://github.com/skanagavelu/algorithams/blob/master/src/sorting/MergeSort.java

package sorting;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
    int[] array = { 5, 6, 10, 3, 9, 2, 12, 1, 8, 7 };
    mergeSort(array, 0, array.length -1);
    System.out.println(Arrays.toString(array));

    int[] array1 = {4, 7, 2};
    System.out.println(Arrays.toString(array1));
    mergeSort(array1, 0, array1.length -1);
    System.out.println(Arrays.toString(array1));
    System.out.println("\n\n");

    int[] array2 = {4, 7, 9};
    System.out.println(Arrays.toString(array2));
    mergeSort(array2, 0, array2.length -1);
    System.out.println(Arrays.toString(array2));
    System.out.println("\n\n");

    int[] array3 = {4, 7, 5};
    System.out.println(Arrays.toString(array3));
    mergeSort(array3, 0, array3.length -1);
    System.out.println(Arrays.toString(array3));
    System.out.println("\n\n");

    int[] array4 = {7, 4, 2};
    System.out.println(Arrays.toString(array4));
    mergeSort(array4, 0, array4.length -1);
    System.out.println(Arrays.toString(array4));
    System.out.println("\n\n");

    int[] array5 = {7, 4, 9};
    System.out.println(Arrays.toString(array5));
    mergeSort(array5, 0, array5.length -1);
    System.out.println(Arrays.toString(array5));
    System.out.println("\n\n");

    int[] array6 = {7, 4, 5};
    System.out.println(Arrays.toString(array6));
    mergeSort(array6, 0, array6.length -1);
    System.out.println(Arrays.toString(array6));
    System.out.println("\n\n");

    //Handling array of size two
    int[] array7 = {7, 4};
    System.out.println(Arrays.toString(array7));
    mergeSort(array7, 0, array7.length -1);
    System.out.println(Arrays.toString(array7));
    System.out.println("\n\n");

    int input1[] = {1};
    int input2[] = {4,2};
    int input3[] = {6,2,9};
    int input4[] = {6,-1,10,4,11,14,19,12,18};
    System.out.println(Arrays.toString(input1));
    mergeSort(input1, 0, input1.length-1);
    System.out.println(Arrays.toString(input1));
    System.out.println("\n\n");

    System.out.println(Arrays.toString(input2));
    mergeSort(input2, 0, input2.length-1);
    System.out.println(Arrays.toString(input2));
    System.out.println("\n\n");

    System.out.println(Arrays.toString(input3));
    mergeSort(input3, 0, input3.length-1);
    System.out.println(Arrays.toString(input3));
    System.out.println("\n\n");

    System.out.println(Arrays.toString(input4));
    mergeSort(input4, 0, input4.length-1);
    System.out.println(Arrays.toString(input4));
    System.out.println("\n\n");
}

private static void mergeSort(int[] array, int p, int r) {
    //Both below mid finding is fine.
    int mid = (r - p)/2 + p;
    int mid1 = (r + p)/2;
    if(mid != mid1) {
        System.out.println(" Mid is mismatching:" + mid + "/" + mid1+ "  for p:"+p+"  r:"+r);
    }

    if(p < r) {
        mergeSort(array, p, mid);
        mergeSort(array, mid+1, r);
//      merge(array, p, mid, r);
        inPlaceMerge(array, p, mid, r);
        }
    }

//Regular merge
private static void merge(int[] array, int p, int mid, int r) {
    int lengthOfLeftArray = mid - p + 1; // This is important to add +1.
    int lengthOfRightArray = r - mid;

    int[] left = new int[lengthOfLeftArray];
    int[] right = new int[lengthOfRightArray];

    for(int i = p, j = 0; i <= mid; ){
        left[j++] = array[i++];
    }

    for(int i = mid + 1, j = 0; i <= r; ){
        right[j++] = array[i++];
    }

    int i = 0, j = 0;
    for(; i < left.length && j < right.length; ) {
        if(left[i] < right[j]){
            array[p++] = left[i++];
        } else {
            array[p++] = right[j++];
        }
    }
    while(j < right.length){
        array[p++] = right[j++];
    } 
    while(i < left.length){
        array[p++] = left[i++];
    }
}

//InPlaceMerge no extra array
private static void inPlaceMerge(int[] array, int p, int mid, int r) {
    int secondArrayStart = mid+1;
    int prevPlaced = mid+1;
    int q = mid+1;
    while(p < mid+1 && q <= r){
        boolean swapped = false;
        if(array[p] > array[q]) {
            swap(array, p, q);
            swapped = true;
        }   
        if(q != secondArrayStart && array[p] > array[secondArrayStart]) {
            swap(array, p, secondArrayStart);
            swapped = true;
        }
        //Check swapped value is in right place of second sorted array
        if(swapped && secondArrayStart+1 <= r && array[secondArrayStart+1] < array[secondArrayStart]) {
            prevPlaced = placeInOrder(array, secondArrayStart, prevPlaced);
        }
        p++;
        if(q < r) {     //q+1 <= r) {
            q++;
        }
    }
}

private static int placeInOrder(int[] array, int secondArrayStart, int prevPlaced) {
    int i = secondArrayStart;
    for(; i < array.length; i++) {
        //Simply swap till the prevPlaced position
        if(secondArrayStart < prevPlaced) {
            swap(array, secondArrayStart, secondArrayStart+1);
            secondArrayStart++;
            continue;
        }
        if(array[i] < array[secondArrayStart]) {
            swap(array, i, secondArrayStart);
            secondArrayStart++;
        } else if(i != secondArrayStart && array[i] > array[secondArrayStart]){
            break;
        }
    }
    return secondArrayStart;
}

private static void swap(int[] array, int m, int n){
    int temp = array[m];
    array[m] = array[n];
    array[n] = temp;
}
}

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

看看合并的一个步骤:

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

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

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

我知道我来晚了，但这是我昨天写的一个解决方案。我也在其他地方发布了这个帖子，但这似乎是SO上最受欢迎的就地合并帖子。我也没有在其他地方看到这个算法，所以希望这能帮助到一些人。

这个算法是最简单的形式，所以它可以被理解。它可以显著地调整以获得额外的速度。平均时间复杂度为:稳定的原地阵列归并为O(n.log₂n)，整体排序为O(n.(log₂n)²)。

//                     Stable Merge In Place Sort
//
//
// The following code is written to illustrate the base algorithm. A good
// number of optimizations can be applied to boost its overall speed
// For all its simplicity, it does still perform somewhat decently.
// Average case time complexity appears to be: O(n.(log₂n)²)

#include <stddef.h>
#include <stdio.h>

#define swap(x, y)    (t=(x), (x)=(y), (y)=t)

// Both sorted sub-arrays must be adjacent in 'a'
// Assumes that both 'an' and 'bn' are always non-zero
// 'an' is the length of the first sorted section in 'a', referred to as A
// 'bn' is the length of the second sorted section in 'a', referred to as B
static void
merge_inplace(int A[], size_t an, size_t bn)
{
    int t, *B = &A[an];
    size_t  pa, pb;     // Swap partition pointers within A and B

    // Find the portion to swap.  We're looking for how much from the
    // start of B can swap with the end of A, such that every element
    // in A is less than or equal to any element in B.  This is quite
    // simple when both sub-arrays come at us pre-sorted
    for(pa = an, pb = 0; pa>0 && pb<bn && B[pb] < A[pa-1]; pa--, pb++);

    // Now swap last part of A with first part of B according to the
    // indicies we found
    for (size_t index=pa; index < an; index++)
        swap(A[index], B[index-pa]);

    // Now merge the two sub-array pairings.  We need to check that either array
    // didn't wholly swap out the other and cause the remaining portion to be zero
    if (pa>0 && (an-pa)>0)
        merge_inplace(A, pa, an-pa);

    if (pb>0 && (bn-pb)>0)
        merge_inplace(B, pb, bn-pb);
} // merge_inplace

// Implements a recursive merge-sort algorithm with an optional
// insertion sort for when the splits get too small.  'n' must
// ALWAYS be 2 or more.  It enforces this when calling itself
static void
merge_sort(int a[], size_t n)
{
    size_t  m = n/2;

    // Sort first and second halves only if the target 'n' will be > 1
    if (m > 1)
        merge_sort(a, m);

    if ((n-m)>1)
        merge_sort(a+m, n-m);

    // Now merge the two sorted sub-arrays together. We know that since
    // n > 1, then both m and n-m MUST be non-zero, and so we will never
    // violate the condition of not passing in zero length sub-arrays
    merge_inplace(a, m, n-m);
} // merge_sort

// Print an array */
static void
print_array(int a[], size_t size)
{
    if (size > 0) {
        printf("%d", a[0]);
        for (size_t i = 1; i < size; i++)
            printf(" %d", a[i]);
    }
    printf("\n");
} // print_array
 
// Test driver
int
main()
{
    int a[] = { 17, 3, 16, 5, 14, 8, 10, 7, 15, 1, 13, 4, 9, 12, 11, 6, 2 };
    size_t  n = sizeof(a) / sizeof(a[0]);
 
    merge_sort(a, n);
 
    print_array(a, n);

    return 0;
} // main