Komplexität:
Beim Mischen werden Q(N) Schlüsselvergleiche gemacht.
Rekursionstiefe logarithmisch beschränkt, insgesamt ergeben sich Q(N log N) Schlüsselvergleiche, denn
C(N) = C(N/2) + C(N/2) + Q(N) = Q(N log N)
Auch Anzahl der Bewegungen ist Q(N log N).
nichtrekursive Varianten: Reines 2-Wege-Mergesort
Es werden jeweils Teilfolgen der Länge 2, 4, 8 usw verschmolzen bis Folge sortiert ist.
Dabei können kürzere Randstücke am rechten Rand übrigbleiben.