|
2.4.1. Beschreibung
Ein Problem beim M-Wege-Mischen ist, daß man 2*m Bänder benötigt. Um diesen Nachteil aufzuheben wurden verschiedene Algorithmen entwickelt. Die bekannteste Methode ist das Mehrphasen Sortieren (polyphase sort).
Die grundlegende Idee besteht darin, daß zu Beginn ein Band, das Ausgabeband, leer bleibt. Auf die restlichen Bänder werden die zu sortierenden Daten vorsortiert verteilt und danach auf das Ausgabeband gemischt. Sind von einem Eingabeband alle Daten gelesen wird es zum Ausgabeband.
2.4.2. Beispiel
Sequenz: 04 06 05 08 09 03 11 20 22
Band A: 04 06|03 11 20 22
Band B: 05 08 09
Band C:
Band A: 03 11 20 22
Band B:
Band C: 04 05 06 08 09
Band A:
Band B: 03 04 05 06 08 09 11 20 22
Band C:
|
