|
2.2.1. Unterschiede
Beim Natürlichen Mischen (natural merge) werden bereits vorhandene sortiere Teilsequenzen berücksichtigt. Die Länge aller gemischten Teilsequenzen im k-ten Durchlauf ist gleich k², unabhängig davon, ob bereits längere Teilsequenzen geordnet sind und gemischt werden könnten.
Eine Teilsequenz wird Lauf genannt, wenn sie folgende Bedingungen erfüllt:
a[n] a[i] i = Beginn der Sequenz
a[j] > a[j+1] j = Ende der Sequenz
2.2.2. Algorithmus
1. Schritt: Mische die zu sortierenden Daten (Band A) in Läufe und schreibe die Läufe abwechselnd in Band B und C.
2. Schritt: Sortiere jeweils einen Lauf aus B und C zu einem neuen Lauf und schreibe die Läufe abwechselnd in Band A. Wiederhole so lange, bis das Band sortiert ist.
2.2.3. Beispiel
Band A: 9 5 2 8 9 0 1 2 unsortierte Sequenz
Band B:
Band C:
Band B: 9|2 8 9
Band C: 5|0 1 2
Band A: 5 9|0 1 2 2 8 9
Band B: 5 9
Band C: 0 1 2 2 8 9
Band A: 0 1 2 2 5 8 9 9 sortierte Sequenz
|
