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

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]" Я понимаю, чтобы выделить дополнительную память для них обоих.

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

Answer 1

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

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

Есть несколько дисперсий, некоторые стабильны, некоторые нестабильные. См. Раздел «Реализация» под Nist Diags. Например.

Answer 2

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

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

Answer 3

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