Mergesort
Mergesort

== Komplexität ==
Mergesort ist ein stabiles Sortierverfahren, vorausgesetzt der Merge-Schritt ist entsprechend implementiert. Seine Komplexität beträgt im Worst-, Best- und Average-Case in Landau-Notation ausgedrückt stets .
Damit ist Mergesort hinsichtlich der Komplexität Quicksort grundsätzlich überlegen, da Quicksort (ohne besondere Vorkehrungen) ein  von  besitzt. Es benötigt jedoch zusätzlichen Speicherplatz (der Größenordnung ), ist also kein In-place-Verfahren.
Für die Laufzeit  von Mergesort bei  zu sortierenden Elementen gilt die Rekursionsformel
Nach dem Master-Theorem kann die Rekursionsformel durch  bzw.  approximiert werden mit jeweils der Lösung (2. Fall des Mastertheorems, s. dort) .
 Durchschnittliche und maximale Anzahl Vergleiche        
Sind  die Längen der zu verschmelzenden und vorsortierten Folgen  dann gilt für die Anzahl  der erforderlichen Vergleiche fürs sortierende Verschmelzen
da erstens eine Folge komplett vor der anderen liegen kann, d. h., es ist  bzw.  oder es ist zweitens  (bzw. umgekehrt), sodass die Elemente bis zum letzten Element in jeder Folge verglichen werden müssen. Dabei ist jeweils angenommen, dass das Vergleichen der zwei Folgen bei den Elementen mit niedrigem Index beginnt. Mit
(Subskript  für ''maximal'') sei die maximale Anzahl der Vergleiche fürs ''Verschmelzen'' bezeichnet.
Für die maximale Anzahl  an Vergleichen für einen ganzen ''Mergesort''-Lauf von  Elementen errechnet sich daraus
Für eine Gleichverteilung lässt sich auch die durchschnittliche Anzahl  (Subskript  für ''durchschnittlich'') der Vergleiche genau berechnen, und zwar ist für 
Dabei ist  die Anzahl der Vergleiche für die Anordnung
wobei  für das letzte (das am höchsten sortierende) Element in der Folge  steht, die (nicht von einem Element aus  unterbrochenen)  zu  gehören und  (die auch fehlen können) entweder zu  oder zu  gehören. Der in den Summenformeln beigegebene Binomialkoeffizient zählt die verschiedenen Möglichkeiten für 
Für die durchschnittliche Anzahl  an Vergleichen für einen ganzen Mergesort-Lauf von  Elementen errechnet man daraus