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
Schlagworte: Algorithmus, Mergesort, Rekursion, sort