Merge insertion

This article was due to content flaws on the quality assurance side of the computer science editorial added. This is done in order to bring the quality of the articles from the subject area of ​​computer science to an acceptable level. Help to eliminate the shortcomings in this article and take part in the discussion !  ( + )

Merge Insertion is a recursive , comparison- oriented sorting method that uses fewer comparisons than mergesort .

Idea of ​​the algorithm

The actual structure of the algorithm is difficult to understand. Therefore, the idea of Merge Insertion should be briefly explained at this point .

Mergesort always requires the same number of comparisons depending on the input length , regardless of whether it is a power of two or not. This fact makes Merge insertion to Use and therefore it creates to manage with less than Compare Mergesort. The idea is not to split up the input during the recursion into partial lists of equal size, but to always process the next higher power of two. As a result, Merge Insertion only requires a very small number of more comparisons than is theoretically necessary in comparison to the information-theoretical lower bound . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle S(n)\geq \lceil \log _{2}n!\rceil }$

running time

Merge insertion has a complexity in the best, average and worst case . ${\displaystyle {\mathcal {O}}(n\cdot \log(n))}$

Algorithm as pseudocode

procedure MergeInsertion ( ): ${\displaystyle S_{1}{,}...{,}S_{n}}$

 1. Sortiere die Eingabe  ${\displaystyle S_{1}{,}...{,}S_{n}}$ mit je einem Vergleich in  ${\displaystyle \lfloor n/2\rfloor }$ disjunkte Paare.
    Ergebnis:  ${\displaystyle b_{i}{<}a_{i}}$ mit  ${\displaystyle i=1{,}...{,}\lfloor n/2\rfloor }$
 2. Sortiere die größeren Elemente  ${\displaystyle a_{1}{,}...{,}a_{\lfloor n/2\rfloor }}$ rekursiv mit MergeInsertion.
 3. Nenne das Ergebnis aus Schritt 2 die Hauptkette:  ${\displaystyle b_{1}{<}a_{1}{<}a_{2}...{<}a_{\lfloor n/2\rfloor }}$
    Füge nun die restlichen Elemente  ${\displaystyle b_{2}{,}...{,}b_{\lceil n/2\rceil }}$ durch Binäres Einfügen in der Reihenfolge 
     ${\displaystyle b_{3},b_{2},b_{5},b_{4},b_{11},b_{10},b_{9},b_{8},b_{7},b_{6},...}$ in die Hauptkette ein.

literature

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

Individual evidence

1. ↑ Wikipedia page on sorting methods