Mergesort

Mergesort ist ein Sortieralgorithmus, der ähnlich wie Quicksort nach dem Prinzip Teile und herrsche (engl. Divide and conquer) arbeitet.

Mergesort betrachtet die zu sortierenden Daten als Liste und zerlegt sie in kleinere Listen, die jede für sich sortiert werden. Die sortierten kleinen Listen werden dann zu größeren Listen zusammengefügt (engl.: to merge), bis wieder eine jetzt sortierte Gesamtliste erreicht ist.

 Startliste   : 8--2--7--1--9--3--6--5

 Nächste Liste: 2--8
 Nächste Liste: 2--8  1--7
 Merge        : 1--2--7--8
 Nächste Liste: 1--2--7--8  3--9
 Nächste Liste: 1--2--7--8  3--9  5--6
 Merge        : 1--2--7--8  3--5--6--9
 Merge        : 1--2--3--5--6--7--8--9

In iterativer Version sieht der Algorithmus also so aus:

 WHILE (Weitere_Elemente_in_Startliste) {
     Nächste_2er_Liste()
     WHILE (Letzte_2_Listen_gleich_lang) {
         Merge()
     }
 }
 WHILE (Mehr_als_1_Liste) {
     Merge()
 }

Da Mergesort die Startliste sowie alle Zwischenlisten sequenziell abarbeitet, eignet er sich besonders zur Sortierung von verketteten Listen. Für Arrays ist ein temporäres Array derselben Länge des zu sortierenden Arrays als Zwischenspeicher nötig (nicht in-place), weshalb hierfür Quicksort meist die bessere Wahl ist.

Mergesort ist stabil, seine Komplexität beträgt in der Landau-Notation ausgedrückt O(n·log(n)).