Mergesort

Mergesort gehört zur Gruppe der asymptodisch optimalen Sortieralgorithmen. Er funktioniert genauso wie Quicksort nach dem "divide-and-conquer"-Verfahren.

Dieses Verfahren bietet die Möglichkeit einer iterativen Implementierung. Außerdem ist die Laufzeit immer optimal. Um dieses Verfahren optimal zu nutzen, wird ein temporäres zweites Feld benötigt.

Weitere Varianten zu diesem Algorithmus finden Sie unter BTMsort.

Der Name "Mergesort" kommt von merge (dt. verschmelzen), da die Grundidee des Verfahrens das Verschmelzen zweier bereits sortierten Felder darstellt.

Die Idee wurde erstmalig von John von Neumann vorgestellt (1945).