Sortiernetze

Das Sortier­verfahren Odd-even Mergesort geht auf K.E. Batcher [Bat 68] zurück. Es basiert auf einem Merge-Verfahren, mit dem zwei sortierte Hälften einer Folge zu einer insgesamt sortierten Folge verschmolzen werden (engl.: to merge – verschmelzen).

Im Gegensatz zu Mergesort ist dieses Verfahren nicht daten­abhängig, d.h. es werden unabhängig von den Daten stets dieselben Vergleiche durchgeführt. Odd-even Mergesort lässt sich daher als Sortiernetz implementieren.

Merge-Verfahren

Es folgt zunächst das Merge-Verfahren, das eine Folge, deren beide Hälften sortiert sind, zu einer sortierten Folge verschmilzt.

Algorithmus oddevenMerge(n)

Eingabe:

Folge a₀, ..., a_n-1 der Länge n > 1, deren beide Hälften a₀, ..., a_n/2-1 und a_n/2, ..., a_n-1 sortiert sind (n Zweierpotenz)

Ausgabe:

Die sortierte Folge

Methode:

1. wenn n > 2 dann
1. wende oddevenMerge(n/2) rekursiv auf die gerade Teilfolge a₀, a₂, ..., a_n-2 und auf die ungerade Teilfolge a₁, a₃, ..., a_n-1 an
2. Vergleich [i:i+1] für alle i ∈ {1, 3, 5, 7, ..., n-3}
2. sonst
1. Vergleich [0:1]

Korrektheit

Die Korrektheit des Merge-Verfahrens lässt sich per Induktion und mit Hilfe des 0-1-Prinzips zeigen.

Ist n = 2¹, so wird mit dem Vergleich [0:1] die Folge sortiert. Sei nun n = 2^k, k > 1 und für alle kleineren k sei das Verfahren korrekt (Induktions­voraussetzung).

Die 0-1-Folge a = a₀, ..., a_n-1 wird gedanklich zeilenweise in ein zwei­spaltiges Feld eingetragen. Die entsprechende Zuordnung der Index­positionen ist in Bild 1a gezeigt, hier für n = 16. In Bild 1b ist die dadurch entstehende Situation dargestellt. Jede der beiden sortierten Hälften der 0-1-Folge beginnt mit einer gewissen Anzahl von Nullen (weiß) und endet mit einer gewissen Anzahl von Einsen (grau).

In der linken Spalte befindet sich die gerade Teilfolge, d.h. alle a_i mit i gerade, also a₀, a₂, a₄ usw.; in der rechten Spalte die ungerade Teilfolge, d.h. alle a_i mit i ungerade, also a₁, a₃, a₅ usw. Wie die ursprüng­liche Folge bestehen auch die gerade und die ungerade Teilfolge jeweils aus zwei sortierten Hälften.

Nach Induktions­voraussetzung werden die linke und rechte Spalte durch rekursive Anwendung von oddevenMerge(n/2) in Schritt 1 des Algorithmus sortiert. Die rechte Spalte kann maximal zwei Einsen mehr enthalten als die linke (Bild 1c).

Durch Anwendung der Vergleiche von Schritt 2 des Algorithmus (Bild 1d) wird in jedem Fall das Feld sortiert (Bild 1e).

Analyse

Mit T(n) sei die Anzahl der von oddevenMerge(n) durch­geführten Vergleiche bezeichnet. Dann gilt für n > 2

T(n)  =  2·T(n/2) + n/2-1

Mit T(2) = 1 ergibt sich

T(n)  =  n/2 · (log(n)-1) + 1  ∈  O(n·log(n))

Sortierverfahren

Aus dem Merge-Verfahren lässt sich durch rekursive Anwendung das Sortier­verfahren Odd-even Mergesort erzeugen.

Algorithmus oddevenMergesort(n)

Eingabe:

Folge a₀, ..., a_n-1 (n Zweierpotenz)

Ausgabe:

Die sortierte Folge

Methode:

1. wenn n > 1 dann
1. oddevenMergesort(n/2) rekursiv auf die beiden Hälften a₀, ..., a_n/2-1 und a_n/2, ..., a_n-1 der Folge anwenden
2. oddevenMerge(n)

Die Anzahl der Vergleicher von Odd-even Mergesort liegt in O(n log(n)²).

Bild 2 zeigt das Odd-even-Mergesort-Sortiernetz für n = 8.

Programm

Es folgt eine Implementation von Odd-even Mergesort in Java. Das Verfahren ist in der Klasse OddEvenMergeSorter gekapselt. Die Methode sort übergibt das zu sortierende Array an das Array a und ruft die Funktion oddEvenMergeSort auf.

Die Funktion oddEvenMergeSort sortiert zunächst rekursiv die beiden Hälften der Folge. Danach verschmilzt sie die beiden Hälften durch Aufruf von oddEvenMerge.

Die Funktion oddEvenMerge verschmilzt eine Folge, deren beide Hälften sortiert sind. Dies geschieht rekursiv durch Anwendung von oddEvenMerge auf die gerade und die ungerade Teilfolge und anschließendes Vergleichen von benachbarten Elementen. Welche Elemente benachbart sind, wird durch einen Parameter r angegeben: In der ursprüng­lichen Folge sind Elemente mit dem Abstand r = 1 benachbart; in der geraden Teilfolge sind Elemente mit dem Abstand r = 2 benachbart; in der geraden Teilfolge der geraden Teilfolge sind Elemente mit dem Abstand r = 4 benachbart usw.

Mit den Anweisungen

wird ein Objekt vom Typ OddEvenMergeSorter erzeugt und anschließend die Methode sort aufgerufen, um ein Array b zu sortieren. Die Länge n des Arrays muss eine Zweierpotenz sein.

Zusammenfassung

Dieselbe asymptotische Komplexität wie Odd-even Mergesort haben auch die Sortiernetze Bitonic Sort und Shellsort. Die Anzahl der Vergleicher von Bitonic Sort nähert sich mit wachsendem n an die Anzahl der Vergleicher von Odd-even Mergesort an. Die Anzahl der Vergleicher von Shellsort ist stets um etwa 33% höher als die von Odd-even Mergesort.

Die folgende Tabelle gibt eine Übersicht über die Anzahl der Vergleicher für n = 4, 16, 64, 256 und 1024.

Literatur

[Bat 68]   K.E. Batcher: Sorting Networks and their Applications. Proc. AFIPS Spring Joint Comput. Conf., Vol. 32, 307-314 (1968)

[Sed 03]   R. Sedgewick: Algorithms in Java, Parts 1-4. 3. Auflage, Addison-Wesley (2003)

[Lan 12]   H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Odd-even Mergesort und andere Sortiernetze, wie etwa Bitonic Sort, sowie die Sortierverfahren Quicksort, Heapsort, Mergesort und Shellsort, finden Sie auch in meinem Buch über Algorithmen.
Weitere Themen des Buches: parallele Sortieralgorithmen, Textsuche, Graphenalgorithmen, algorithmische Geometrie, Arithmetik, Codierung, Kryptografie, NP-Vollständigkeit, formale Verifikation.

[Weitere Informationen]