Кнут оставил это как упражнение (Том 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 рано или поздно.
Осталась ли рабочая область, которая содержит только 1/4 элемента, достаточно большой для объединения
А и Б? К сожалению, это не так.
Тем не менее, второе упомянутое ограничение дает нам подсказку, что мы можем использовать его, расположив рабочую область таким образом, чтобы она перекрывалась с любым вложенным массивом, если мы сможем обеспечить последовательность слияния так, чтобы не объединенные элементы не были перезаписаны.
На самом деле, вместо сортировки второй половины рабочей области, мы можем отсортировать первую половину и поместить рабочую область между двумя отсортированными массивами следующим образом:
... sorted 1/4 array B | unsorted work area | ... sorted 1/2 array A ...
Эти установочные эффекты организуют перекрытие рабочей области с подмассивом A. Эта идея
предлагается в [Юрки Катаяйнен, Томи Пасанен, Юкка Теухола. `` Практическая сортировка на месте ''. Nordic Journal of Computing, 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 определен ранее.
Полный исходный код можно найти здесь и подробное объяснение можно найти здесь
Кстати, эта версия не самая быстрая сортировка слиянием, потому что ей нужно больше операций подкачки. Согласно моему тесту, это быстрее, чем стандартная версия, которая выделяет дополнительные пробелы в каждой рекурсии. Но он медленнее оптимизированной версии, которая заранее удваивает исходный массив и использует его для дальнейшего слияния.