Merge Insertion

Merge Insertion (auch bekannt a​ls Ford-Johnson-Algorithmus) i​st ein rekursives, vergleichsorientiertes Sortierverfahren, d​as mit weniger Vergleichen a​ls Mergesort auskommt.

Beteilige dich an der Diskussion!
Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+)

Idee des Algorithmus

Der tatsächliche Aufbau d​es Algorithmus i​st schwer z​u verstehen. Deshalb s​oll an dieser Stelle d​ie Idee v​on Merge Insertion k​urz erläutert werden.

Mergesort benötigt immer die gleiche Anzahl Vergleiche abhängig von der Eingabelänge , egal ob 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 nur eine sehr geringe Anzahl Vergleiche mehr, als theoretisch notwendig.

Laufzeit

Merge Insertion hat im Best-, Average- und Worst-Case eine -Komplexität.[1][2]

Algorithmus als Pseudocode

procedure MergeInsertion():

 1. Sortiere die Eingabe  mit je einem Vergleich in  disjunkte Paare.
    Ergebnis:  mit 
 2. Sortiere die größeren Elemente  rekursiv mit MergeInsertion.
 3. Nenne das Ergebnis aus Schritt 2 die Hauptkette: 
    Füge nun die restlichen Elemente  durch Binäres Einfügen in der Reihenfolge 
     in die Hauptkette ein.

Literatur

  • Donald E. Knuth: Sorting and Searching/The Art of Computer Programming. Addison-Wesley Longman, 2. Auflage, 2003, ISBN 0201896850

Einzelnachweise

  1. Wikipediaseite zu Sortierverfahren
  2. Florian Stober, Armin Weiß: On the Average Case of MergeInsertion. Abgerufen am 20. Januar 2022.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.