~2026-15680-6: /* Literatur */Online verfügbar.

2026-01-31T19:48:52Z

Literatur: Online verfügbar.

Neue Seite

{{QS-Informatik}}
'''Merge Insertion''' (auch bekannt als Ford-[[Selmer M. Johnson|Johnson]]-Algorithmus) ist in der [[Informatik]] ein [[Rekursion|rekursives]], vergleichsorientiertes [[Sortierverfahren]], das mit weniger Vergleichen als [[Mergesort]] auskommt.

== Idee des Algorithmus ==
Der tatsächliche Aufbau des Algorithmus ist schwer zu verstehen. Deshalb soll an dieser Stelle die Idee von ''Merge Insertion'' kurz erläutert werden.

Mergesort benötigt immer die gleiche Anzahl Vergleiche abhängig von der Eingabelänge <math>n</math>, egal ob <math>n</math> eine Zweierpotenz ist oder nicht. Diese Tatsache macht sich ''Merge Insertion'' zu Nutze und schafft es deshalb, mit weniger Vergleichen als Mergesort auszukommen. Die Idee ist, die Eingabe bei der [[Rekursion]] nicht in möglichst gleich große Teillisten aufzuspalten, sondern immer die nächstgrößere Zweierpotenz zu bearbeiten. Dadurch benötigt ''Merge Insertion'' im Vergleich zur informationstheoretischen unteren Schranke <math>S(n)\ge \lceil \log_2 n! \rceil</math> nur eine sehr geringe Anzahl Vergleiche mehr, als theoretisch notwendig.

== Laufzeit ==
Merge Insertion hat im Best-, Average- und Worst-Case eine <math>\mathcal{O}( n \cdot \log (n) )</math>-Komplexität.<ref>[[Sortierverfahren#Vergleichsbasiertes Sortieren|Wikipediaseite zu Sortierverfahren]]</ref><ref>{{Internetquelle |autor=Florian Stober, Armin Weiß |url=https://arxiv.org/abs/1905.09656v1 |titel=On the Average Case of MergeInsertion |abruf=2022-01-20}}</ref>

== Algorithmus als Pseudocode ==
procedure MergeInsertion(<math>S_1{,}...{,}S_n</math>):

1. Sortiere die Eingabe <math>S_1{,}...{,}S_n</math> mit je einem Vergleich in <math>\lfloor n/2 \rfloor</math> disjunkte Paare.
Ergebnis: <math>b_i{<}a_i</math> mit <math>i=1{,}...{,}\lfloor n/2 \rfloor</math>
2. Sortiere die größeren Elemente <math>a_1{,}...{,}a_{\lfloor n/2 \rfloor}</math> rekursiv mit MergeInsertion.
3. Nenne das Ergebnis aus Schritt 2 die Hauptkette: <math>b_1{<}a_1{<}a_2...{<}a_{\lfloor n/2 \rfloor}</math>
Füge nun die restlichen Elemente <math>b_2{,}...{,}b_{\lceil n/2 \rceil}</math> durch ''Binäres Einfügen'' in der Reihenfolge
<math>b_3,b_2,b_5,b_4,b_{11},b_{10},b_9,b_8,b_7,b_6,...</math> in die Hauptkette ein.

== Literatur ==
* [[Donald E. Knuth]]: [https://seriouscomputerist.atariverse.com/media/pdf/book/Art%20of%20Computer%20Programming%20-%20Volume%203%20(Sorting%20&%20Searching).pdf ''Sorting and Searching/The Art of Computer Programming'']. Addison-Wesley Longman, 2. Auflage, 2003, ISBN 0201896850

== Einzelnachweise ==
<references />

[[Kategorie:Sortieralgorithmus]]

Merge Insertion - Versionsgeschichte

~2026-15680-6: /* Literatur */Online verfügbar.