In-place Merge sort praktische Verwendung

Question

Ich habe versucht, hier und da zu finden, was genau in-move merge sort und wo ich es verwenden muss? Aber keine klare Antwort gefunden. Bitte helfen Sie mir, indem Sie unten antworten.

1) Wann und wo eine direkte Zusammenführung erforderlich ist? Praktische Verwendung von In-Place-Merge.

2) Was passiert, wenn die Eingangsarrays für die In-Place-Zusammenführung nicht sortiert sind?

3) Was isst mehr Speicher zum Sortieren zwischen Merge-Sortierung, In-Place-Merge-Sortierung und Schnell-Sortierung?

Hinweis: Ich frage nach "std :: inplace_merge", das ist ein STL-Algorithmus.

Answer 1

1) In-Place-Zusammenführungssortierung wird verwendet, wenn Sie eine Liste in O (nlogn) -Zeit sortieren möchten, während Sie weniger Speicherplatz als Standard-Mergesort verwenden.

2) Der ganze Zweck der Sortierung ist die Sortierung der Eingabearrays, so dass nicht sortierte Eingabearrays nach dem In-Place-Mergesort sortiert werden.

3) Mergesort verwendet mehr Arbeitsspeicher, da es zwei neue Arrays halber Größe für die beiden rekursiven Aufrufe erstellt. In-Place-Merge-Sort und Quick-Sort sollten ungefähr den gleichen Platz einnehmen, da sie beide an Ort und Stelle sind. Für den Mergesort bedeutet Inplace O (log n) extra space aus dem Beibehalten der relevanten Indizes des Arrays der Länge n, nicht der strengsten O (1) Bedeutung von in-place. Quicksort benötigt im schlimmsten Fall O (nlogn) zusätzlichen Platz, da es O (n) rekursive Aufrufe geben kann, von denen jeder Zeiger hat, die Speicherplatz O (logn) einnehmen.

Hoffe, das hilft.