Aufruf z.B. mit
produziert
Mergesort ist ein schneller Algorithmus zum sortieren von Elementen. Er wurde bereits 1945 vorgestellt.
Vorgehensweise
Als erstes teilt man die zu sortierende Liste in der Mitte in 2 Teillisten, um diese dann wieder zu teilen bis man nur noch Listen mit max. zwei Elementen hat. Diese kleinen Listen kann man dann sehr einfach sortieren. Danach werden die kleinen Listen schrittweise wieder zu großen Listen zusammengefügt, wobei man darauf bauen kann, dass alle Listen sortiert sind. Man fügt aber immer nur 2 Listen zu einer Neuen zusammen, weil man sich dabei immer nur die ersten Elemente der beiden Liste ansehen muss. Diese Funktion ist sehr gut durch Rekursion lösbar. Am Ende erhält man das Ergebnis als zusammengesetzte sortierte Liste.
Beispiel
Quelle: http://upload.wikimedia.org/wikipedia/de/thumb/9/99/Mergesort_example.png/600px-Mergesort_example.png
Mit Quicksort kann man sehr schnell und Ressourcen sparend sortieren. Den Algorithmus gibt es bereits seit 1960!
Vorgehensweise am Beispiel einer Liste mit Zahlen:
Zuerst wählt man ein zufälliges Pivot-Element (Drehpunktelement). Danach sortiert man die verbleibenden Elemente in 2 Listen, in der Ersten sind alle Elemente die kleiner oder gleich dem Pivot-Element sind, in der Zweiten alle die größer oder gleich sind. Das Pivot-Element merkt man sich – man kann es jetzt bereits als Fertig markieren – und wendet das gleiche Verfahren auf die beiden kleineren Listen an.
Beispiel:
Pseudocode und weitere Beispiele: siehe Wikipedia.