Mergesort

Drucken

Das Verfahren erzeugt eine sortierte Folge durch das Verschmelzen einzelner Teilfolgen. Dieses Verschmelzen wird in einem externen Feld druchgeführt, weshalb man mergesort zu den externen Sortierverfahren zählt. Im nebenstehenden Applet wird dieser Algorithmus abgebildet. Eine mögliche Implementierung wird im untenstehenden Script erläutert. Diese beruht auf der Auslagerung des Mischvorganges in eine separate Methode _partition.

Mergesort wurde 1945 durch John von Neumann vorgestellt. Da der Algorithmus das Problem auf die Zerlegung von Teilproblemen abstützt, arbeitet er nach dem Prinzip Teile und herrsche (divide and conquer).


  , Script zu Sortierverfahren