如何使用合并sortingalgorithm就地sorting？
我知道这个问题不是太具体。
我想要的是有人告诉我如何将正常的合并sorting转换为就地合并sorting（或具有恒定额外空间开销的合并sorting）。
我能find的所有网页都是“太复杂”或“超出本文范围”的页面。
唯一已知的就地合并（没有任何额外的空间）的方法太复杂，不能简化为实际的程序。 （ 从这里拿）
即使它太复杂了， 如何进行合并sorting的基本概念是什么？
克努特留下这个练习（第3卷，5.2.5）。 确实存在就地合并sorting。 必须认真执行。
首先， 这里描述的天真就地合并不是正确的解决scheme。 它将性能降至O（N 2 ） 。
我们的想法是对数组的一部分进行sorting，而将其余部分用作合并工作区。
例如下面的合并函数。
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 ，两个sorting的子数组分别表示为范围[i, m)和[j, n) 。 工作区域从w开始。 与大多数教科书中给出的标准合并algorithm相比，该algorithm交换了sorting后的子arrays和工作区之间的内容。 结果，前一个工作区域包含合并的已sorting元素，而存储在工作区域中的前一个元素则移至两个子数组。
但是，有两个约束必须得到满足：
- 工作区域应该在数组的范围内。 换句话说，它应该足够大，以保持交换的元素，而不会造成任何过度的错误;
- 工作区可以与两个sorting的数组中的任何一个重叠，但是应该确保没有任何未合并的元素被覆盖;
通过定义这种合并algorithm，很容易想象一个解决scheme，它可以sorting一半的数组; 接下来的问题是如何处理存储在工作区中的其余部分，如下所示：
... unsorted 1/2 array ... | ... sorted 1/2 array ...
一个直观的想法是recursionsorting工作区域的另一半，因此只有1/4个元素尚未被sorting。
... unsorted 1/4 array ... | sorted 1/4 array B | sorted 1/2 array A ...
在这个阶段的关键点是，我们必须早晚sortingsorting后的1/4元素B和sorting的1/2元素A.
工作区域是否只剩下1/4个元素，足以将A和B合并？ 不幸的是，事实并非如此。
但是，上面提到的第二个约束给了我们一个提示，我们可以利用它来安排工作区与任何一个子数组重叠，如果我们能够确保合并顺序的话，那些未合并的元素将不会被覆盖。
实际上，我们可以不对工作区的后半部分进行sorting，而是对前半部分进行sorting，并将工作区放在两个sorting后的数组之间：
... sorted 1/4 array B | unsorted work area | ... sorted 1/2 array A ...
这种设置效果将工作区域与子arraysA重叠。这个想法在[Jyrki Katajainen，Tomi Pasanen，Jukka Teuhola中提出。 “实用的in-place mergesort''。 北欧计算机学报，1996年]。
所以唯一剩下的就是重复上述步骤，这样就减less了1/2，1/4，1/8 …的工作区域。当工作区域变得足够小的时候，例如只剩下两个元素，我们可以切换到一个简单的插入sorting来结束这个algorithm。
这里是基于本文的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的地方。
完整的源代码可以在这里find，详细的解释可以在这里find
顺便说一句，这个版本不是最快的合并sorting，因为它需要更多的交换操作。 根据我的testing，它比标准版本更快，在每次recursion中都会分配额外的空间。 但是它比优化后的版本要慢，这个版本提前将原始数组加倍，并将其用于进一步合并。
包括它的“大成果”，本文描述了几种就地合并sorting（PDF）的变体：
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf
用较less的移动就地sorting
Jyrki Katajainen，Tomi A. Pasanen
它表明，可以使用O（1）额外空间，O（n log n / log log n）元素移动和n log 2 n + O（n log log n）比较来sortingn个元素的数组。 这是第一个在最坏情况下需要o（n log n）移动的就地sortingalgorithm，同时保证O（n log n）的比较，但是由于涉及常数因素，algorithm主要是理论上的兴趣。
我认为这也是相关的。 我有一个躺在地上的打印输出，由一位同事传给我，但是我没有看到它。 它似乎涵盖了基本的理论，但是我对这个话题的认识还不够全面：
http://comjnl.oxfordjournals.org/cgi/content/abstract/38/8/681
最佳稳定合并
安东尼奥斯Symvonis
本文展示了如何稳定地将两个序列A和B分别与O（m + n）赋值O（mlog（n / m + 1））进行比较，并使用一个常量额外的空间量。 这个结果匹配所有已知的下限…
关键的一步是让合并本身到位。 这些消息来源并不难，但是当你尝试的时候你会失去一些东西。
看一下合并的一个步骤：
[… list- sorted … | x … list- A … | y … list- B …]
我们知道sorting后的序列比其他所有东西都less， x小于A中的其他所有元素， y小于B中的所有其他元素 。 在x小于或等于y的情况下，只需将指针移到A的开始位置即可。 在y小于x的情况下，必须将整个A sorting 。 最后一步是什么让这个昂贵（除了在退化的情况下）。
它通常更便宜（特别是当数组实际上只包含每个元素的单个词，例如指向一个string或结构的指针）时间换取一些空间，并有一个单独的临时数组，您可以在它们之间来回sorting。
这真的不容易或有效率，我build议你不要这样做，除非你真的必须这样做（并且你可能不必这样做，因为就地合并的应用大部分是理论上的，因此这是家庭作业）。 你不能使用quicksort吗？ 无论如何，使用一些简单的优化，Quicksort将会更快，而其额外的内存是O（log N） 。
无论如何，如果你必须这样做，那么你必须。 这是我发现的： 一个和两个 。 我不熟悉就地合并sorting，但似乎基本思想是使用旋转来促进两个数组合并，而不使用额外的内存。
请注意，这比传统的合并sorting还要慢。
仅供参考，这里是一个稳定的就地合并sorting的很好的实现 。 复杂，但不是太糟糕。
我最终实现了一个稳定的就地合并sorting和一个稳定的Java 就地快速sorting 。 请注意复杂度是O（n（log n）^ 2）
C中的无缓冲mergesort的一个例子
#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 (@pb) if not found. */ { int i; for ( i = ba; 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 (@pb) if not found. */ { int i; for ( i = ba; 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, nh); ip_merge_(v, v+h, v+n); } }
自适应mergesort（优化）的一个例子。
添加支持代码和修改，以便在任何大小的辅助缓冲区可用时加速合并（仍然可以在没有附加内存的情况下工作）。 使用前向和后向合并，循环旋转，小序列合并和sorting以及迭代合并。
#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); }
这是我的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--; } } }
使用Kronrod的原始技术，就地合并sorting有一个相对简单的实现，但实现起来更简单。 一个说明这种技术的图例可以在这里find： http : //www.logiccoder.com/TheSortProblem/BestMergeInfo.htm 。
也有与这个链接相关的作者更详细的理论分析的链接。
我只是尝试使用插入sortingalgorithm在JAVA中合并sorting合并algorithm，使用以下步骤。
1）有两个sorting的数组可用。
2）比较每个数组的第一个值; 并将最小的值放入第一个数组中。
3）使用插入sorting将较大的值放入第二个数组（从左到右）。
4）然后再次比较第一个数组的第二个值和第二个数组的第一个值，并且做同样的事情。 但是当交换发生时，有一些线索可以比较其他项目，但只需要交换。
我在这里做了一些优化。 在插入sorting中保持较less的比较。
我发现这个解决scheme唯一的缺点是需要在第二个数组中更大的数组元素交换。
例如）
First___Array：3，7，8，9
第二arrays：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; } }
Swift中mergesort的一个例子。
func mergeAndSort (array: Array<UInt32>) -> Array<UInt32> { let halfIndex = array.count / 2 let leftArray = Array(array[0..<halfIndex]) let rightArray = Array(array[halfIndex..<array.count]) let sortedLeftArray = (leftArray.count == 1) ? leftArray : mergeAndSort(leftArray) var sortedRightArray = (rightArray.count == 1) ? rightArray : mergeAndSort(rightArray) var sortedArray: Array<UInt32> = [] var rightI = 0 var leftI = 0 while(leftI < sortedLeftArray.count) { if sortedLeftArray[leftI] < sortedRightArray[rightI] { sortedArray.append(sortedLeftArray[leftI]) leftI++ } else { sortedArray.append(sortedRightArray[rightI]) rightI++ } if leftI == sortedLeftArray.count { for i in rightI..<sortedRightArray.count { sortedArray.append(sortedRightArray[i]) } } if rightI == sortedRightArray.count { for i in leftI..<sortedLeftArray.count { sortedArray.append(sortedLeftArray[i]) } break } } return sortedArray } var unsortedArray: Array<UInt32> = [] for i in 0...22 { let randomNumber = arc4random_uniform(100) unsortedArray.append(randomNumber) } var sortedArray = mergeAndSort(unsortedArray)
