Кнут оставил это как упражнение (Том 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. `` Практическая сортировка слиянием на месте ''. 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 определено ранее.
Полный исходный код можно найти здесь, а подробное объяснение можно найти здесь
Кстати, эта версия не самая быстрая сортировка слиянием, потому что для нее требуется больше операций подкачки. Согласно моему тесту, это быстрее, чем стандартная версия, которая выделяет лишние пробелы в каждой рекурсии. Но он медленнее, чем оптимизированная версия, которая заранее удваивает исходный массив и использует его для дальнейшего слияния.
person
Larry LIU Xinyu
schedule
27.03.2013
