Sortieren auf zweidimensionalen Prozessorfeldern

Ein besonders einfaches und gut zu implementierendes Verfahren ist das Verfahren 4-way-Mergesort von Schimmler [Schi 87].

Verfahren

Der Algorithmus 4-way-Mergesort beruht auf einem Merge-Verfahren, welches vier grob­sortierte k/2×k/2-Felder zu einem grob­sortierten k×k-Feld vereinigt.

Prozedur 4-way-merge(k)

Eingabe:

k×k-Feld, dessen vier k/2×k/2-Felder grobsortiert sind

Ausgabe:

Das grobsortierte k×k-Feld

Methode:

1. Sortieren der Zeilen der Teilfelder:
1. aufsteigend in den oberen Teilfeldern,
2. absteigend in den unteren Teilfeldern;
2. Sortieren der Spalten;
3. Sortieren der Zeilen:
1. ungerade Zeilen aufsteigend,
2. gerade Zeilen absteigend;
4. Sortieren der Spalten;

Die Korrektheit der Prozedur 4-way-merge kann in sehr anschau­licher Weise mithilfe des 0-1-Prinzips gezeigt werden. (Das 0-1-Prinzip gilt auch für den Begriff "grobsortiert", da durch anschließendes Sortieren der Zeilen der sortierte Zustand herbei­geführt werden kann.)

Ausgangs­situation ist ein nur mit Nullen und Einsen belegtes Feld, dessen vier Teilfelder grobsortiert sind. In Bild 1a ist diese Situation dargestellt (Nullen sind weiß dargestellt, Einsen grau).

Nach dem Sortieren der Zeilen der Teilfelder in Schritt 1 ergibt sich Bild 1b.

Nach dem Sortieren der Spalten in Schritt 2 ergeben sich zwei grob­sortierte k×k/2-Felder (Bild 1c).

Nach dem gegenläufigen Sortieren der Zeilen in Schritt 3 sind zwei unter­schiedliche Situationen möglich: entweder befinden sich die "gemischten" Halbzeilen (d.h. Halbzeilen in denen sowohl Nullen als auch Einsen vorkommen) aus Bild 1c in ver­schiedenen Hälften (Bild 1d) oder in der gleichen Hälfte des Feldes (in Bild 1e in der rechten Hälfte). Dies hängt von der Anzahl der vollständig mit Einsen belegten Halbzeilen ab.

In beiden Fällen jedoch führt das Sortieren der Spalten in Schritt 4 zu der in Bild 1f gezeigten Situation, nämlich einem grob­sortierten k×k-Feld.

Bild 1: Beweis der Korrektheit der Prozedur 4-way-merge mit Hilfe des 0-1-Prinzips

Durch rekursive Anwendung der Prozedur 4-way-merge kann ein völlig unsortiertes Feld grobsortiert werden:

Prozedur roughsort(k)

Eingabe:

Unsortiertes k×k-Feld

Ausgabe:

Das grobsortierte k×k-Feld

Methode:

1. wenn k > 1 dann
1. roughsort(k/2) auf die vier k/2×k/2-Teilfelder anwenden;
2. 4-way-merge(k);

Ein n×n-Feld wird sortiert, indem es zunächst grobsortiert wird und dann die Zeilen sortiert werden:

Algorithmus 4-way-Mergesort(n)

Eingabe:

Unsortiertes n×n-Feld

Ausgabe:

Das sortierte n×n-Feld

Methode:

1. roughsort(n);
2. Zeilen sortieren;

Dem 0-1-Prinzip zufolge sortiert das Verfahren jeden beliebigen Datensatz, da es nach obiger Argumentation alle 0-1-Datensätze sortiert.

Analyse

Die Analyse der Prozedur 4-way-merge ergibt folgendes, wenn das Sortieren einer Zeile bzw. Spalte der Länge k mit Odd-even Trans­position Sort k Schritte dauert:

In Schritt 4 sind nur k/2 Schritte von Odd-even Trans­position Sort erforderlich, da jede Spalte aus zwei ineinander ver­schränkten sortierten Teilfolgen besteht.

Der Algorithmus 4-way-Mergesort benötigt für die rekursive Ausführung von 4-way-merge im Aufruf von roughsort insgesamt 3n + 3n/2 + 3n/4 + ... + 3 ≤ 6n Schritte. Für das anschließende Sortieren der Zeilen sind noch einmal n Schritte erforderlich, sodass sich insgesamt ergibt:

T(n) ≤ 7n

Zusammenfassung

Der vorgestellte Algorithmus 4-way-Mergesort zum Sortieren eines n×n-Feldes hat die gleiche asymptotische Zeit­komplexität wie der Algorithmus von Thompson-Kung [TK 77], nämlich O(n). Hinsichtlich der Konstanten ist er jedoch um einen Faktor von gut 2 schlechter. Die Qualität des Algorithmus liegt in seiner Einfachheit bei gleich­zeitiger asymptotischer Optimalität.

Eine Implementierung des Algorithmus auf einem befehls­systolischen Feld ist in [Schi 87] sowie in [Lan 90] angegeben.

Literatur

[Lan 90]   H.W. Lang: Das befehlssystolische Prozessorfeld -- Architektur und Programmierung. Dissertation, Christian-Albrechts-Universität Kiel (1990)

[Schi 87]   M. Schimmler: Fast Sorting on the Instruction Systolic Array. Bericht Nr. 8709, Institut für Informatik, Christian-Albrechts-Universität Kiel (1987)

[TK 77]   C.D. Thompson, H.T. Kung: Sorting on a Mesh-Connected Parallel Computer. Communications of the ACM, 20, 4, 263-271 (1977)