Lar*_*nyu 131
Knuth将此作为练习(Vol 3,5.2.5).确实存在就地合并排序.必须谨慎实施.
首先,天真就地合并,例如描述这里是不是正确的解决方案.它将性能降级为O(N 2).
我们的想法是对数组的一部分进行排序,同时将其余部分用作合并的工作区域.
例如,作为以下合并功能.
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.
顺便说一句,这个版本不是最快的合并排序,因为它需要更多的交换操作.根据我的测试,它比标准版本更快,标准版本在每次递归中分配额外的空格.但它比优化版本慢,后者使原始阵列提前翻倍,并将其用于进一步合并.
Ste*_*sop 58
包括其"重大结果",本文描述了几种就地合并排序(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 log 2 n + O(n log log n)比较来对n个元素的数组进行排序.这是第一个就地排序算法,在最坏的情况下需要o(n log n)移动,同时保证O(n log n)比较,但由于所涉及的常数因素,算法主要是理论上的兴趣.
我认为这也是相关的.我有一张打印出来的照片,由同事传给我,但我还没读过.它似乎涵盖了基本理论,但我对该主题不够熟悉,无法判断如何全面:
http://comjnl.oxfordjournals.org/cgi/content/abstract/38/8/681
最佳稳定合并
Antonios Symvonis
本文展示了如何稳定地合并大小为m和n,m≤n的两个序列A和B,分别为O(m + n)分配,O(mlog(n/m + 1))比较并仅使用常数额外空间的数量.这个结果匹配所有已知的下界...
IVl*_*lad 10
这真的不容易或有效,我建议你不要这样做,除非你真的必须这样做(你可能不必这样做,除非这是家庭作业,因为合并的应用主要是理论上的).你不能使用quicksort吗？无论如何,Quicksort会更快,只需更简单的优化,其额外内存为O(log N).
无论如何,如果你必须这样做,那么你必须.这是我发现的:一和二.我不熟悉inplace合并排序,但似乎基本的想法是使用旋转来促进合并两个数组而不使用额外的内存.
请注意,这比不在适当位置的经典合并排序要慢.
Don*_*ows 10
关键步骤是使合并本身就位.这并不像那些消息来源那么困难,但是当你尝试时会丢失一些东西.
看一下合并的一个步骤:
[... list- sorted ... | x ... list- A ... | y ... list- B ...]
我们知道排序的序列比其他任何东西都要少,x比A中的其他所有东西都小,而且y比B中的其他东西要少.在x小于或等于y的情况下,只需将指针移动到A的开头即可.在y小于x的情况下,你必须在整个A之间移动y来进行排序.最后一步是使这种代价变得昂贵(除了退化情况).
它通常更便宜(特别是当数组实际上每个元素实际上只包含单个单词时,例如,指向字符串或结构的指针)来换取一些空间的时间并且有一个单独的临时数组,您可以在它们之间来回切换.
#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);
}
这个答案有一个代码示例，它实现了Bing-Chao Huang 和 Michael A. Langston的论文Practical In-Place Merging 中描述的算法。我不得不承认我不了解细节，但合并步骤的给定复杂度是 O(n)。
从实践的角度来看，有证据表明纯就地实现在现实世界场景中的表现并不好。例如，C++ 标准定义了std::inplace_merge，顾名思义就是就地合并操作。
假设 C++ 库通常被很好地优化，看看它是如何实现的很有趣：
实现委托给__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) 时间内运行。
看起来很像。它委托给一个函数，该函数也尝试分配一个缓冲区。根据它是否有足够的元素，它会选择实现。常量内存回退函数称为__buffered_inplace_merge。
也许即使回退仍然是 O(n) 时间，但关键是如果临时内存可用，他们不使用实现。
请注意，C++ 标准通过将所需的复杂度从 O(n) 降低到 O(N log N) 来明确赋予实现选择这种方法的自由：
复杂性： 如果有足够的额外内存可用，正好是 N-1 次比较。如果内存不足，O(N log N) 次比较。
当然，这不能作为证明永远不应该使用 O(n) 时间内的常量空间就地合并。另一方面，如果它会更快，优化的 C++ 库可能会切换到这种类型的实现。