Top-Down-Mergesort (Algorithmus 2.4)

So geht’s: Oben steht der Rekursionsbaum: Jeder Streifen ist ein Aufruf sortiere(a, lo, hi) über genau den Plätzen, die er sortiert. Orange ist der aktuelle Aufruf, blau umrandet sind die Aufrufe, die auf seine Rückkehr warten, hellblau die fertigen. Unter den Balken steht das Hilfsarray aux: Beim merge wird der Bereich dorthin kopiert, dann wandert Schritt für Schritt das kleinere der beiden vorderen Elemente (orange, sein Vergleichspartner blau) zurück nach a[k] (grün). „Bis gemergt“ springt zum Ende des nächsten merge. Das Protokoll zeigt wie Abbildung 2.11 das Array nach jedem merge, eingerückt nach Rekursionstiefe.

Erklärung

Top-Down-Mergesort (Algorithmus 2.4) arbeitet nach „Teile und herrsche“: Array halbieren, beide Hälften rekursiv sortieren, dann die zwei sortierten Hälften zu einem sortierten Ganzen zusammenführen (mergen).

Der Code:

• aux ist ein Hilfsarray, das nur einmal angelegt wird, damit nicht bei jedem Rekursionsschritt neuer Speicher entsteht.
• sort(a, lo, hi): Ist der Bereich höchstens ein Element groß (hi <= lo), ist er schon sortiert, Rekursion endet.
• Sonst Mitte berechnen, linke Hälfte lo..mid sortieren, rechte Hälfte mid+1..hi sortieren, dann merge.
• merge (Listing 2.9, hier nicht abgedruckt) kopiert den Bereich nach aux und läuft mit zwei Zeigern durch beide Hälften. Jeweils das kleinere der beiden vorderen Elemente kommt zurück nach a.

Die Tabelle zeigt jeden merge-Aufruf an MERGESORTEXAMPLE:

• merge(a, 0, 0, 1): M und E → E M
• merge(a, 2, 2, 3): R und G → G R
• merge(a, 0, 1, 3): EM + GR → E G M R
• So wächst es von unten: erst Paare, dann Vierer, dann Achter, zuletzt merge(a, 0, 7, 15) mit den beiden sortierten Hälften EEGMORRS und AEELMPTX zum Endergebnis.

Kosten:

• Vergleiche: zwischen ½ N lg N und N lg N, und zwar garantiert, auch im schlimmsten Fall. Das ist der große Sprung gegenüber den N² der elementaren Verfahren.
• Zusatzspeicher: proportional zu N für aux. Das ist der Haken, Mergesort sortiert nicht in place.
• Stabil: Gleiche Elemente behalten ihre Reihenfolge.

Rekursionsbaum: lg N Ebenen, auf jeder Ebene wird insgesamt N mal gemergt, daher N lg N. Genau das beschreibt der Text unten auf der Seite mit den 2^k Teilarrays auf Ebene k.