Wikipedia · einfach zusammengefasst · Stand
Merge Insertion
Merge Insertion (auch bekannt als Ford-Johnson-Algorithmus) ist in der Informatik ein rekursives, vergleichsorientiertes Sortierverfahren, das mit weniger …
Inhalt4 Abschnitte
Grundidee und Bedeutung
Merge Insertion, auch Ford-Johnson-Algorithmus genannt, ist ein rekursives, vergleichsorientiertes Sortierverfahren. Es ordnet eine Eingabe anhand von Vergleichen und benötigt dabei weniger Vergleiche als Mergesort.
Der zentrale Ansatz besteht darin, die Eingabe während der Rekursion nicht möglichst gleichmäßig aufzuteilen. Stattdessen bearbeitet Merge Insertion jeweils die nächstgrößere Zweierpotenz. Dadurch liegt die Zahl der Vergleiche nur geringfügig über der informationstheoretischen unteren Schranke S(n) ≥ ⌈log₂ n!⌉. Diese Schranke beschreibt die theoretisch notwendige Mindestzahl von Vergleichen zum Sortieren von n Elementen.
Paarbildung und rekursives Sortieren
Zunächst werden die Eingabeelemente S₁, …, Sₙ mit jeweils einem Vergleich zu ⌊n/2⌋ disjunkten Paaren zusammengefasst. In jedem Paar wird das kleinere Element bᵢ und das größere Element aᵢ genannt:
bᵢ < aᵢ für i = 1, …, ⌊n/2⌋.
Anschließend werden die größeren Elemente a₁, …, a⌊n/2⌋ rekursiv mit Merge Insertion sortiert. Das Ergebnis bildet die Hauptkette:
b₁ < a₁ < a₂ … < a⌊n/2⌋.
Die übrigen Elemente b₂, …, b⌈n/2⌉ werden danach in diese bereits sortierte Hauptkette eingefügt.
Einfügen in die Hauptkette
Das Einfügen der restlichen Elemente erfolgt durch binäres Einfügen, also mithilfe einer schrittweisen Suche in der sortierten Hauptkette. Die Einfügereihenfolge ist:
b₃, b₂, b₅, b₄, b₁₁, b₁₀, b₉, b₈, b₇, b₆, …
Auf diese Weise wird die Hauptkette schrittweise zu einer vollständig sortierten Folge ergänzt. Der Algorithmus verbindet somit Paarvergleiche, rekursives Sortieren der größeren Elemente und das anschließende Einfügen der kleineren Elemente.
Laufzeit und Vergleichsaufwand
Im Best Case, im Average Case und im Worst Case besitzt Merge Insertion die Komplexität O(n · log(n)).
Sein besonderer Vorteil liegt nicht in einer anderen asymptotischen Laufzeit als bei typischen effizienten Sortierverfahren, sondern in der geringen Zahl benötigter Vergleiche. Im Vergleich zu Mergesort kann Merge Insertion mit weniger Vergleichen auskommen und bleibt dabei nahe an der unteren Schranke ⌈log₂ n!⌉.
