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

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

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

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

看看合并的一个步骤:

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

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

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

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

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

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