如何使用合并排序算法进行就地排序？

#1 楼

克努斯（Knuth）将此作为练习（第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。
可以在此处找到完整的源代码，在这里可以找到详细的解释
版本不是最快的合并排序，因为它需要更多的交换操作。根据我的测试，它比标准版本更快，后者在每次递归中都分配了额外的空间。但这比优化版本要慢，后者要预先将原始数组加倍并将其用于进一步合并。

#2 楼

包括其“重大成果”在内，本文描述了就地合并排序（PDF）的几种变体：

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

更少的移动就地排序

Jyrki Katajainen，Tomi A. Pasanen



显示了可以使用O（1）
多余空间，O（n log n / log log n）
元素移动以及n log2n + O（n log
log n）比较。这是第一个
就地排序算法，它要求
o（n log n）在最坏的情况下移动
同时保证O（n log n）
比较，但是由于算法所涉及的常数
主要是理论意义。


我认为这也很重要。我有它的打印输出，是由一位同事传给我的，但是我还没有看过。它似乎涵盖了基础理论，但是我对这个主题是否足够全面，无法全面判断：

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

最佳稳定合并

Antonios Symvonis


本文说明如何稳定地合并两个序列A和B分别使用O（m + n）
赋值，O（mlog（n / m + 1））
比较并仅使用常量的m和
n，m≤n
额外的空间量。此
结果匹配所有已知的下限...

#3 楼

这确实不是容易或高效的，并且我建议您除非确实需要，否则不要这样做（并且除非您是家庭作业，否则您可能不必这样做，因为就地合并的应用大部分是理论上的）。您不能使用quicksort吗？无论如何，Quicksort都会通过一些更简单的优化而变得更快，并且它的额外内存为O（log N）。

无论如何，如果必须这样做，那么必须这样做。我发现的是：一和二。我不熟悉就地合并排序，但是似乎基本的想法是使用旋转来方便地合并两个数组，而无需使用额外的内存。

请注意，这比经典的合并还要慢排序不到位。

#4 楼

关键步骤是使合并本身就位。这并不像这些资料来源所讲的那么难，但是尝试时会丢失一些东西。

查看合并的一个步骤：


[...列表排序的... | x ...列表-A ... | y ...列表-B ...]


我们知道排序的序列小于x小于A中的所有其他元素，y小于B中的其他所有元素。在x小于或等于y的情况下，只需将指针移动到A的起始位置就可以了。在y小于x的情况下，您必须将y洗牌超过整个A进行排序。最后一步是使它变得昂贵的原因（在退化的情况下除外）。

通常更便宜（尤其是当数组每个元素实际上只包含单个单词时，例如指向字符串或结构的指针）权衡一些时间，并有一个单独的临时数组，您可以在它们之间来回排序。

#5 楼

仅供参考，这是一个稳定的就地合并排序的不错的实现。很复杂，但还不算太糟。

我最终用Java实现了稳定的就地合并排序和稳定的就地快速排序。请注意，复杂度为O（n（log n）^ 2）

#6 楼

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

#7 楼

这个答案有一个代码示例，该示例实现了黄冰超和Michael A. Langston在论文《实用就地合并》中描述的算法。我必须承认我不了解细节，但是合并步骤的给定复杂度是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（N log N），显着地赋予了实现者选择这种方法的自由：

< br：复杂度：
如果有足够的额外内存可用，则为N-1个比较。如果内存不足，则进行O（N log N）个比较。


当然，不能以此作为证明永远不使用O（n）时间中的恒定空间就地合并的证明。另一方面，如果速度更快，则优化的C ++库可能会切换到该类型的实现。

#8 楼

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

#9 楼

使用Kronrod的原始技术有一个相对简单的就地合并排序实现，但是实现起来比较简单。可以在以下位置找到说明此技术的图形示例：http://www.logiccoder.com/TheSortProblem/BestMergeInfo.htm。

还存在与该链接相关的同一作者更详细的理论分析的链接。

#10 楼

我只是尝试通过以下步骤使用插入排序算法在JAVA中进行就地合并算法进行合并排序。
1）有两个排序后的数组。
2）比较每个数组的第一个值；并将最小值放入第一个数组中。
3）使用插入排序（从左到右遍历）将较大的值放入第二个数组中。
4）然后再次比较第一个数组的第二个值数组和第二个数组的第一个值，并执行相同的操作。但是，当发生交换时，有一些线索可以跳过比较其他项的步骤，而只是需要交换。

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

例如）

第一个___ 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;
}
}