Merge Sort: Sind die zusätzlichen Array Kopien notwendig?

Question

„Introduction to Algorithms“ der Merge-Sort-Algorithmus mit einer Hilfsfunktion namens MERGE(A, p, q, r) implementiert - die zwei zuvor sortierten Sequenzen fusioniert.

Diese Funktion stellt zwei zusätzliche Arrays L und 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]
.....

Mit dem "create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]" verstehe ich für beide zusätzlichen Speicher zuzuweisen.

Ist es möglich, neu zu schreiben diese Funktion, so dass ich nicht den zusätzlichen Speicher benötigen, und direkt an A zu betreiben?

Answer 1

Klar. Es wird an Ort und Stelle Mergesort genannt.

Wikipedia sagen, es ist kompliziert - aber es ist nicht immer wahr. Einige sind nicht so hoch wie andere , wenn Sie kümmern sich nicht um die Laufzeit .

Es gibt ein paar Varianz, einige stabil sind, einige sind nicht stabil. Siehe "Implementierung" unter NIST DIAGS für einige Beispiel.

Answer 2

Ja, es an Ort und Stelle Mergesort genannt, aber als Wikipedia sagt:

  

In-Place-Sortierung ist möglich (zum Beispiel Listen anstatt Arrays), ist aber sehr kompliziert und wird wenige Leistungssteigerungen in der Praxis bieten, auch wenn der Algorithmus läuft in O (n log n) Zeit. (Katajainen, Pasanen & Teuhola 1996)

Answer 3

Das ist möglich. http://www.diku.dk/hjemmesider/ansatte/jyrki/Paper /mergesort_NJC.ps