Mergesort, allgemeines Sortierverfahren zum Sortieren von n Elementen.

Das Verfahren beruht auf dem Divide-and- Conquer Prinzip. Ist eine (o.B.d.A. aufwärts zu sortierende) Eingabefolge F_e, bestehend aus n Elementen, gegeben, so wird diese Eingabefolge F_e in zwei Teilfolgen \({F}_{e}^{(1)}\) und \({F}_{e}^{(2)}\), bestehend aus \([\frac{n}{2}]\) bzw. \([\frac{n}{2}]-1\) Elementen, aufgespaltet. Diese Teilfolgen \({F}_{e}^{(1)}\) und \({F}_{e}^{(2)}\) werden rekursiv aufwärts sortiert. \({F}_{a}^{(1)}\) bezeichne die zu \({F}_{e}^{(1)}\) gehörige sortierte Teilfolge, \({F}_{a}^{(2)}\) die zu \({F}_{e}^{(2)}\) gehörige sortierte Teilfolge.

Der Zusammensetzungsschritt besteht aus bis zu n Teilschritten. Es werden in jedem Schritt die jeweils ersten Elemente der beiden Teilfolgen \({F}_{a}^{(1)}\) und \({F}_{a}^{(2)}\) betrachtet. Das kleinste dieser beiden Elemente wird hinten an die anfangs leere Ausgabefolge F_a angefügt und aus der entsprechenden Teilfolge gelöscht. Ist eine der beiden Teilfolgen leer, so wird die andere an das Ende der Ausgabefolge angefügt. Nach diesem Zusammensetzungsschritt, der in der Literatur auch Mischen genannt wird, ist die Ausgabefolge eine sortierte Liste.

Sortieren durch Mischen benötigt zum Sortieren von n Elementen höchstens c · n · [log₂n] Schritte. Hierbei bezeichnet c eine von n unabhängige Konstante.