Mergesort

Fakten

• 1945 von John von Neumann erfunden
• Stabiles Sortierverfahren
• Best- und Worst-Case Performance O(n*log(n))
• Nutzen des Teile-und-Herrsche-Algorithmus
• Verfahren:
  1. Falls nur ein Element in der Liste ist, gebe die Liste zurück
  2. Teile die unsortierte Liste rekursiv in 2 gleich große Teillisten (so genannte runs) bis die Liste nicht mehr geteilt werden kann
  3. Füge die kleinen Listen in geordneter Reihenfolge zusammen bis nur eine sortierte Liste übrig bleibt
• Effektiver Nutzen:
  1. Datenstrukturen ohne direkten Zugriff auf Elemente (verkettete Listen)
  2. Externes Sortieren, wenn RAM zu klein ist
• Ableitung Timsort (von Mergesort und Insertionsort): Erkenne schon sortierte Teile der Liste und erstelle daraus die Teillisten --> Best-Case Performance O(n)