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

我知道我来晚了，但这是我昨天写的一个解决方案。我也在其他地方发布了这个帖子，但这似乎是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

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;
}
}

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

C语言中无缓冲区归并排序的一个例子。

#define SWAP(type, a, b) \
    do { type t=(a);(a)=(b);(b)=t; } while (0)

static void reverse_(int* a, int* b)
{
    for ( --b; a < b; a++, b-- )
       SWAP(int, *a, *b);
}
static int* rotate_(int* a, int* b, int* c)
/* swap the sequence [a,b) with [b,c). */
{
    if (a != b && b != c)
     {
       reverse_(a, b);
       reverse_(b, c);
       reverse_(a, c);
     }
    return a + (c - b);
}

static int* lower_bound_(int* a, int* b, const int key)
/* find first element not less than @p key in sorted sequence or end of
 * sequence (@p b) if not found. */
{
    int i;
    for ( i = b-a; i != 0; i /= 2 )
     {
       int* mid = a + i/2;
       if (*mid < key)
          a = mid + 1, i--;
     }
    return a;
}
static int* upper_bound_(int* a, int* b, const int key)
/* find first element greater than @p key in sorted sequence or end of
 * sequence (@p b) if not found. */
{
    int i;
    for ( i = b-a; i != 0; i /= 2 )
     {
       int* mid = a + i/2;
       if (*mid <= key)
          a = mid + 1, i--;
     }
    return a;
}

static void ip_merge_(int* a, int* b, int* c)
/* inplace merge. */
{
    int n1 = b - a;
    int n2 = c - b;

    if (n1 == 0 || n2 == 0)
       return;
    if (n1 == 1 && n2 == 1)
     {
       if (*b < *a)
          SWAP(int, *a, *b);
     }
    else
     {
       int* p, * q;

       if (n1 <= n2)
          p = upper_bound_(a, b, *(q = b+n2/2));
       else
          q = lower_bound_(b, c, *(p = a+n1/2));
       b = rotate_(p, b, q);

       ip_merge_(a, p, b);
       ip_merge_(b, q, c);
     }
}

void mergesort(int* v, int n)
{
    if (n > 1)
     {
       int h = n/2;
       mergesort(v, h); mergesort(v+h, n-h);
       ip_merge_(v, v+h, v+n);
     }
}

一个自适应归并排序的例子(优化)。

添加支持代码和修改，以在任何大小的辅助缓冲区可用时加速合并(在没有额外内存的情况下仍然可以工作)。使用前向和后向合并、环旋转、小序列合并和排序以及迭代合并排序。

#include <stdlib.h>
#include <string.h>

static int* copy_(const int* a, const int* b, int* out)
{
    int count = b - a;
    if (a != out)
       memcpy(out, a, count*sizeof(int));
    return out + count;
}
static int* copy_backward_(const int* a, const int* b, int* out)
{
    int count = b - a;
    if (b != out)
       memmove(out - count, a, count*sizeof(int));
    return out - count;
}

static int* merge_(const int* a1, const int* b1, const int* a2,
  const int* b2, int* out)
{
    while ( a1 != b1 && a2 != b2 )
       *out++ = (*a1 <= *a2) ? *a1++ : *a2++;
    return copy_(a2, b2, copy_(a1, b1, out));
}
static int* merge_backward_(const int* a1, const int* b1,
  const int* a2, const int* b2, int* out)
{
    while ( a1 != b1 && a2 != b2 )
       *--out = (*(b1-1) > *(b2-1)) ? *--b1 : *--b2;
    return copy_backward_(a1, b1, copy_backward_(a2, b2, out));
}

static unsigned int gcd_(unsigned int m, unsigned int n)
{
    while ( n != 0 )
     {
       unsigned int t = m % n;
       m = n;
       n = t;
     }
    return m;
}
static void rotate_inner_(const int length, const int stride,
  int* first, int* last)
{
    int* p, * next = first, x = *first;
    while ( 1 )
     {
       p = next;
       if ((next += stride) >= last)
          next -= length;
       if (next == first)
          break;
       *p = *next;
     }
    *p = x;
}
static int* rotate_(int* a, int* b, int* c)
/* swap the sequence [a,b) with [b,c). */
{
    if (a != b && b != c)
     {
       int n1 = c - a;
       int n2 = b - a;

       int* i = a;
       int* j = a + gcd_(n1, n2);

       for ( ; i != j; i++ )
          rotate_inner_(n1, n2, i, c);
     }
    return a + (c - b);
}

static void ip_merge_small_(int* a, int* b, int* c)
/* inplace merge.
 * @note faster for small sequences. */
{
    while ( a != b && b != c )
       if (*a <= *b)
          a++;
       else
        {
          int* p = b+1;
          while ( p != c && *p < *a )
             p++;
          rotate_(a, b, p);
          b = p;
        }
}
static void ip_merge_(int* a, int* b, int* c, int* t, const int ts)
/* inplace merge.
 * @note works with or without additional memory. */
{
    int n1 = b - a;
    int n2 = c - b;

    if (n1 <= n2 && n1 <= ts)
     {
       merge_(t, copy_(a, b, t), b, c, a);
     }
    else if (n2 <= ts)
     {
       merge_backward_(a, b, t, copy_(b, c, t), c);
     }
    /* merge without buffer. */
    else if (n1 + n2 < 48)
     {
       ip_merge_small_(a, b, c);
     }
    else
     {
       int* p, * q;

       if (n1 <= n2)
          p = upper_bound_(a, b, *(q = b+n2/2));
       else
          q = lower_bound_(b, c, *(p = a+n1/2));
       b = rotate_(p, b, q);

       ip_merge_(a, p, b, t, ts);
       ip_merge_(b, q, c, t, ts);
     }
}
static void ip_merge_chunk_(const int cs, int* a, int* b, int* t,
  const int ts)
{
    int* p = a + cs*2;
    for ( ; p <= b; a = p, p += cs*2 )
       ip_merge_(a, a+cs, p, t, ts);
    if (a+cs < b)
       ip_merge_(a, a+cs, b, t, ts);
}

static void smallsort_(int* a, int* b)
/* insertion sort.
 * @note any stable sort with low setup cost will do. */
{
    int* p, * q;
    for ( p = a+1; p < b; p++ )
     {
       int x = *p;
       for ( q = p; a < q && x < *(q-1); q-- )
          *q = *(q-1);
       *q = x;
     }
}
static void smallsort_chunk_(const int cs, int* a, int* b)
{
    int* p = a + cs;
    for ( ; p <= b; a = p, p += cs )
       smallsort_(a, p);
    smallsort_(a, b);
}

static void mergesort_lower_(int* v, int n, int* t, const int ts)
{
    int cs = 16;
    smallsort_chunk_(cs, v, v+n);
    for ( ; cs < n; cs *= 2 )
       ip_merge_chunk_(cs, v, v+n, t, ts);
}

static void* get_buffer_(int size, int* final)
{
    void* p = NULL;
    while ( size != 0 && (p = malloc(size)) == NULL )
       size /= 2;
    *final = size;
    return p;
}
void mergesort(int* v, int n)
{
    /* @note buffer size may be in the range [0,(n+1)/2]. */
    int request = (n+1)/2 * sizeof(int);
    int actual;
    int* t = (int*) get_buffer_(request, &actual);

    /* @note allocation failure okay. */
    int tsize = actual / sizeof(int);
    mergesort_lower_(v, n, t, tsize);
    free(t);
}

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

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

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