Das Applet ist hier.
Unter Mischen verstehen wir die Kombination von zwei oder mehr geordneten Folgen in eine einzelne geordnete Folge. Zum Beispiel koennen wir die zwei Folgen 503 703 765 und 087 512 677 mischen, und erhalten 087 503 512 677 703 765. Ein einfacher Weg, das zu erreichen ist, die zwei kleinsten Elemente der beiden Folgen zu vergleichen und das kleinere auszugeben.
Aus
503 703 765
087 512 677
entnehmen wir 087 und erhalten
503 703 765
512 677
und in unserer sortierten Folge
087
Diesen Prozess setzen wir fort mit den verbleibenden Folgen.
Der Aufwand fuer diesen Algorithmus ist proportional zu m+n, so
dass klar ist, dass Mischen ein einfacherer Prozess als Sortieren
ist. Ausserdem koennen wir das Problem des Sortierens auf das
Problem des Mischens reduzieren, indem wir immer laengere Teilfolgen
mischen bis alles sortiert ist.
Geschichtlich gesehen war MergeSort eines der ersten Sortierverfahren
fuer das Sortieren auf dem Computer. John von Neumann hat den natuerlichen
Mergesort bereits 1945 vorgestellt.