Merge Sort

Merge Sort teilt das Array, sortiert rekursiv und verschmilzt zwei sortierte Hälften. Zeit $\Theta(n \log n)$, zusätzlicher linearer Speicher.

Stabil und vorhersehbar. Gut als Lehrbeispiel für Divide-and-Conquer.

$$T(n)=2T(n/2)+\Theta(n)$$

Zwei sortierte Folgen mischen: Merge Sorted Array [1].

Wo gebraucht

Stabile $O(n \log n)$-Referenz, externe Sortierung (Runs auf Platte), TimSort-Vorfahre. Parallelisierbar über unabhängige Hälften.

Vertiefung

Merge Sort zerlegt die Eingabe rekursiv in Hälften, sortiert beide Teile und führt sie geordnet zusammen. Beim Mischen zeigt je ein Zeiger auf das kleinste noch nicht übernommene Element jeder Hälfte. Das kleinere wird ausgegeben, bis eine Hälfte erschöpft ist.

Die Rekursion hat logarithmisch viele Ebenen, und pro Ebene werden insgesamt alle Elemente verarbeitet. Klassische Arrayimplementierungen verwenden einen zusätzlichen Puffer in der Grössenordnung der Eingabe. Bei Gleichheit zuerst aus der linken Hälfte zu übernehmen erhält Stabilität.

Schwierigkeitsstufen

1. Zwei sortierte Folgen mit Zeigern verschmelzen.
2. Arbeit pro Rekursionsebene und Zahl der Ebenen verbinden.
3. Puffer wiederverwenden und stabile Gleichheitsbehandlung sichern.

Fallstricke

Nach der Hauptschleife müssen die verbleibenden Elemente der nicht erschöpften Hälfte kopiert werden. Falsche Intervallgrenzen führen besonders bei ungeraden Längen zu verlorenen oder doppelt verarbeiteten Elementen.