EMZETT.Kurz erklärt
Mergesort teilt die Liste in zwei Hälften, sortiert beide rekursiv und mischt (engl. merge) die sortierten Hälften zu einer sortierten Liste. Es arbeitet in jedem Fall in O(n log n) und ist stabil.
Genauer
Anders als Quicksort hat Mergesort keinen schlechten Sonderfall; dafür braucht es zusätzlichen Speicher von O(n). Es eignet sich gut für verkettete Listen und für das Sortieren von Daten, die nicht in den Arbeitsspeicher passen (externes Sortieren).