Adaptiertes 2-Phasen-2-Band-Mischen

Das 2-Phasen-2-Band-Mischen ist ein Sortieralgorithmus.

In den Anfängen der elektronischen Datenverarbeitung wurden Massendaten auf Magnetbändern abgelegt. Diese Bänder wurden mit einem Magnetkopf sequentiell gelesen und geschrieben. Es war also kein wahlfreier Zugriff möglich. Man behalf sich mit Algorithmen, die ein Band mithilfe eines zweiten (u.U. auch eines dritten) sequentiell sortierten.

Dieses Verfahren wurde Ende der 90er Jahre für doppelt verkettete Listen adaptiert (Markus v. Brevern und Dirk Sorges).

Doppelt verkettete Listen bestehen aus Listenenelementen, die einen Zeiger auf den Nachfolger und auf den Vorgänger besitzen. Man kann also vom Anfang vorwärts oder vom Ende rückwärts durch die Listen laufen. Einfügen und Löschen ist sehr einfach. Eine Liste ist einem Array bei diesen beiden Operationen deutlich überlegen.

Im 2-Phasen-2-Band-Mischen werden in einer Phase Läufe (runs) sortierter Elemente bestimmt. Diese Läufe werden dann in der zweiten Phase ineinander gemischt, so dass aus 2 Läufen einer wird. Der Algorithmus endet, wenn nur noch ein (jetzt vollständig sortierter) Lauf übrig bleibt.

Bei doppelt verketteten Listen verwendet man die Vorwärtszeiger als Zeiger auf das nächste Element und die Rückwärtszeiger als Zeiger auf den nächsten Lauf. Man initialisiert die Liste, indem man für jedes Element die Rückwärtszeiger wie die Vorwärtszeiger auf das nächste Element zeigen lässt. Jetzt hat man n Läufe der Länge 1. Daraufhin sortiert man so lange zwei Läufe zusammen, bis nur noch ein Lauf übrig ist. Das Sortieren erreicht man mit zwei zusätzlichen Zeigern, die jeweils auf einen Lauf zeigen. Das kleinere referenzierte Element wird in den Mischlauf übernommen, der entsprechende Zeiger auf das nächste Element des Laufs gesetzt. Ist ein Lauf ganz abgearbeitet, wird der Rest des anderen Laufs an den Mischlauf angehängt. Anhängen und Einsortieren wird einfach durch "Umzeigern" erreicht. Abschließend werden alle Rückwärtszeiger auf das jeweils vorige Element gesetzt.

Dieses Verfahren arbeitet In-place, verbraucht also keinen weiteren Speicherplatz. Kopiert wird nichts, lediglich die Zeiger werden verändert. Der Aufwand liegt immer in O( n * log n). Es ist also das perfekte Sortierverfahren für unbestimmte Datenlagen.