Сортировка слиянием: Нужны ли дополнительные копии массива?

Question

В разделе «Введение в алгоритмы» алгоритм сортировки слиянием реализован с помощью вспомогательной функции с именем MERGE(A, p, q, r), которая объединяет две ранее отсортированные последовательности.

Эта функция вводит два дополнительных массива L и R.

MERGE(A, p, q, r)
1 n1 ← q − p + 1
2 n2 ←r − q
3 create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
.....

К "create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]" Я понимаю, как выделить дополнительную память для них обоих.

Можно ли переписать эту функцию, чтобы мне не требовалась дополнительная память, и работать напрямую с A?

Answer 1

Конечно. Это называется сортировкой слиянием на месте.

Википедия говорят, что это сложно - но это не всегда так. Некоторые не такие сложные, как другие , если вы не заботитесь о времени выполнения .

Есть несколько отклонений, некоторые стабильны, некоторые нестабильны. См. Раздел «реализация» в разделе NIST DIAGS , где приведен пример.

Answer 2

Это возможно. http://www.diku.dk/hjemmesider/ansatte/jyrki/Paper/mergesort_NJC.ps

Answer 3

Да, это называется сортировкой слиянием на месте, но, как говорит Википедия :

Сортировка на месте возможна (например, с использованием списков, а не массивов), но она очень сложна и на практике даст небольшой выигрыш в производительности, даже если алгоритм выполняется за O (n log n) времени. (Katajainen, Pasanen & Teuhola 1996)