2.1.1. Algorithmus
Schritt 1: Zerlege die Sequenz A in zwei Hälften B und C.
Schritt 2: Mische B und C durch Kombination einzelner Elemente zu geordneten Paaren.
Schritt 3: Schreibe die gemischte Sequenz auf A und wiederhole die Schritte 1 und 2, wobei die geordneten Paare zu geordneten Quadrupeln zusammengefaßt werden.
Schritt 4: Wiederhole die voranstehenden Schritte durch mischen der Quadrupel zu Octupel und fahre damit so lange fort bis die Sequenz geordnet ist. Bei jedem Schritt wird die Länge der gemischten Sequenz verdoppelt.
2.1.2. Beispiel
Band A: 9 5 2 8 9 0 1 2 unsortierte Sequenz
Band B:
Band C:
Band B: 9|2|9|1
Band C: 5|8|0|2
Band A: 5 9|2 8|0 9|1 2
Band B: 5 9|0 9
Band C: 2 8|1 2
Band A: 2 5 8 9|0 1 2 9
Band B: 2 5 8 9
Band C: 0 1 2 9
Band A: 0 1 2 2 5 8 9 9 sortierte Sequenz
|