German English

Sorting nets

Bitonic sort
The Bitonic Sort [Bat 68] sorting process is one of the fastest sorting networks. With a sorting
network [Knu 73] [CLRS 01], the order of comparisons does not depend on the data, unlike
sorting methods such as quicksort or heapsort . The method is therefore particularly suitable for
implementation in hardware. It is also the basis of many parallel sorting processes on two-
dimensional processor fields .
2
The sorting network Bitonic Sort contains Θ( n log( n ) ) comparators. It therefore has the same
asymptotic complexity as the sorting networks Odd-even Mergesort and Shellsort . Although
there is a sorting network with only O ( n log( n )) comparators [AKS 83] , it is slower than Bitonic
Sort for all practical problem sizes due to its high constant .
The Bitonic Sort sorting network is developed below based on the 0-1 principle. The 0-1
principle states that a comparator network that sorts all sequences of 0s and 1s is a sorting
network, i.e. it then also sorts any sequence of arbitrary input values.

Basics

Definition: A sequence a = a , ..., a n with a i ∈ {0, 1}, i = 0, ..., n -1 is called a 0-1

0 -1
sequence .
1
A 0-1 sequence is called bitonic , ) if it contains at most two alternations between 0 and 1,
i.e. if numbers k , m ∈ {1, ..., n } exist such that
a , ..., a k =0, a k , ..., a m =1, a m , ..., a n = 0 or
0 -1 -1 -1
a , ..., a k =1, a k , ..., a m =0, a m , ..., a n = 1.
0 -1 -1 -1

Various examples of bitonic 0-1 sequences are shown schematically in Figure 1 below (zeros
white, ones gray):

Bild 1: Verschiedene Beispiele bitonischer 0-1-Folgen

Definition: Sei n ∈ ℕ, n gerade. Das Vergleichernetz Bn ist wie folgt definiert:

Bn = [0 : n/2] [1 : n/2+1] ... [n/2-1 : n-1].
Als Beispiel ist in Bild 2 das Vergleichernetz B8 dargestellt.

Bild 2: Vergleichernetz B8

Satz: Sei n ∈ ℕ, n gerade und a = a0, ..., an-1 eine bitonische 0-1-Folge. Die Anwendung des
Vergleichernetzes Bn auf a ergibt dann
Bn(a) = b0, ..., bn/2-1 c0, ..., cn/2-1,
wobei die bi die kleineren Elemente und die cj die größeren Elemente sind, d.h.
bi≤cj für alle i, j ∈ {0, ..., n/2-1},
und darüber hinaus gilt
b0, ..., bn/2-1 ist bitonische 0-1-Folge und
c0, ..., cn/2-1 ist bitonische 0-1-Folge.

Beweis: Sei a = a0, ..., an-1 eine bitonische 0-1-Folge. Schreibt man a in zwei Zeilen, dann
ergibt sich folgendes Bild (Nullen sind wieder weiß, Einsen grau dargestellt). Die Folge
beginnt mit Nullen, dann kommen Einsen und dann wieder Nullen (Bild 3a). Oder die Folge
beginnt mit Einsen, dann kommen Nullen und dann wieder Einsen (Bild 3b).
Es sind noch eine ganze Reihe anderer Variationen möglich, einige sind in Bild 4
dargestellt. Eine Anwendung des Vergleichernetzes Bn entspricht einem Vergleich zwischen
oberer und unterer Zeile; hierdurch wird in allen Fällen die im Satz angegebene Form
hergestellt, d.h. alle bi sind kleiner oder gleich allen cj und b ist bitonisch und c ist bitonisch.

Bild 3: Bitonische 0-1-Folgen (dargestellt jeweils in zwei Zeilen)

 Bild 4: Anwendung des Vergleichernetzes Bn auf bitonische 0-1-Folgen

Sortiernetz BitonicSort

Vergleichernetze Bk für verschiedene Zweierpotenzen k bilden die Bausteine für das Sortiernetz
BitonicSort(n). Durch Anwendung des Divide-and-Conquer-Prinzips werden Vergleichernetze
BitonicMerge und BitonicSort konstruiert.
Das Vergleichernetz BitonicMerge(n) sortiert eine bitonische Folge. Aufgrund der Tatsache, dass
Bn wiederum bitonische Teilfolgen halber Länge liefert, von denen die erste die kleineren
Elemente enthält und die zweite die größeren, lässt es sich rekursiv aufbauen (Bild 5).
Die bitonische Folge, die als Eingabe für BitonicMerge notwendig ist, wird aus einer aufsteigend
sortierten und einer absteigend sortierten Hälfte zusammengesetzt. Diese sortierten Hälften
werden durch rekursive Anwendung von BitonicSort erzeugt (Bild 6).

Bild 5: BitonicMerge(n)
 Bild 6: BitonicSort(n)

Im darauf folgenden Bild 7 ist als Beispiel das Sortiernetz BitonicSort(8) dargestellt.
Auf das ganze Vergleichernetz lässt sich das 0-1-Prinzip anwenden: da das Vergleichernetz
BitonicSort beliebige 0-1-Folgen sortiert, sortiert es auch jede beliebige andere Folge, ist also
ein Sortiernetz.

Bild 7: Sortiernetz BitonicSort für n=8

Analyse

Das Vergleichernetz BitonicMerge(n) besteht aus log(n) Vergleicherstufen (so etwa die letzten
3 = log(8) Vergleicherstufen in Bild 7). Die Anzahl der Vergleicherstufen T(n) des gesamten
Sortiernetzes BitonicSort(n) ergibt sich also wie folgt:
T(n) = log(n) + T(n/2) sowie
T(1) = 0.
Die Lösung dieser Rekursionsgleichung ist
T(n) = log(n) + log(n)-1 + log(n)-2 + ... + 1 = log(n)·(log(n)+1) / 2.
Jede Vergleicherstufe des Sortiernetzes besteht aus n/2 Vergleichern; insgesamt sind dies also
Θ(n log(n)2) Vergleicher.

Programm

Es folgt eine Implementation von Bitonic Sort in Java. Das Verfahren ist in der Klasse
BitonicSorter gekapselt. Die Methode sort übergibt das zu sortierende Array an das Array a und
ruft bitonicSort auf.
Die Funktion bitonicSort erzeugt zunächst eine bitonische Folge, indem sie die beiden Hälften
der Folge gegenläufig sortiert (durch zwei rekursive Aufrufe von bitonicSort). Danach sortiert sie
die bitonische Folge durch Aufruf von bitonicMerge.
Die Funktion bitonicMerge sortiert rekursiv eine bitonische Folge a. Die zu sortierende Folge
beginnt am Index lo, die Anzahl der Elemente ist n, die Sortierrichtung ist aufsteigend, wenn dir
= ASCENDING, sonst absteigend.
Ein Vergleicher wird durch die Funktion compare modelliert. Der Parameter dir gibt die
Sortierrichtung an. Die Elemente a[i] und a[j] werden vertauscht, wenn dir = ASCENDING und
(a[i] > a[j]) = true oder wenn dir = DESCENDING und (a[i] > a[j]) = false gilt.
Mit den Anweisungen
BitonicSorter s=new BitonicSorter();
[Link](b);
wird ein Objekt vom Typ BitonicSorter erzeugt und anschließend die Methode sort aufgerufen,
um ein Array b zu sortieren. Die Länge n des Arrays muss eine Zweierpotenz sein (vgl. Bitonic
Sort für beliebiges n).

public class BitonicSorter

{
private int[] a;
// sorting direction:
private final static boolean ASCENDING=true, DESCENDING=false;

public void sort(int[] a_)

{
a=a_;
bitonicSort(0, [Link], ASCENDING);
}

private void bitonicSort(int lo, int n, boolean dir)

{
if (n>1)
{
int m=n/2;
bitonicSort(lo, m, ASCENDING);
bitonicSort(lo+m, m, DESCENDING);
bitonicMerge(lo, n, dir);
}
}

private void bitonicMerge(int lo, int n, boolean dir)

{
if (n>1)
{
int m=n/2;
for (int i=lo; i<lo+m; i++)
compare(i, i+m, dir);
bitonicMerge(lo, m, dir);
bitonicMerge(lo+m, m, dir);
}
}
 private void compare(int i, int j, boolean dir)
{
if (dir==(a[i]>a[j]))
exchange(i, j);
}

private void exchange(int i, int j)

{
int t=a[i];
a[i]=a[j];
a[j]=t;
}

} // end class BitonicSorter

Zusammenfassung

Mit Θ(n log(n)2) Vergleichern ist das Verfahren Bitonic Sort nicht optimal – die untere Schranke
für Sortierverfahren, die auf Vergleichen beruhen, liegt bei Ω(n log(n)) und wird z.B. von
Heapsort auch erreicht. Dennoch ist Bitonic Sort insbesondere für Hardware- und
Parallelrechner-Realisierungen interessant, da die Reihenfolge der Vergleiche von vornherein
festliegt und nicht von den Daten abhängig ist.
The procedure can also be adapted for any n that is not a power of two ( Bitonic Sort for any n ).

literature

[AKS 83] M. Ajtai, J. Komlos, E. Szemeredi : An O(n log n) Sorting Network. Proceedings of
the 25th ACM Symposium on Theory of Computing, 1-9 (1983)
[Bat 68] KE Batcher : Sorting Networks and their Applications. Proc. AFIPS Spring Joint
Comput. Conf., Vol. 32, 307-314 (1968)
[CLRS 01] TH Cormen, CE Leiserson, RL Rivest, C. Stein : Introduction to Algorithms. 2nd
edition, The MIT Press (2001)
[Knu 73] DE Knuth : The Art of Computer Programming, Vol. 3 - Sorting and Searching.
Addison Wesley (1973)
[Lan 12] HW Lang : Algorithms in Java. 3rd edition, Oldenbourg (2012)
Bitonic Sort and other sorting networks, such as Odd-even Mergesort , as well as the sorting
methods Quicksort , Heapsort , Mergesort and Shellsort , can also be found in my book on
algorithms.
Other topics in the book: parallel sorting algorithms, text search, graph algorithms, algorithmic
geometry, arithmetic, coding, cryptography, NP-completeness, formal verification.

[Additional Information]
1
) from English bi tonic = double mono tonic

Continue with: [up]

HW Lang mail@[Link] Imprint Data Protection

Created: February 2nd, 1997 Updated: February 5th, 2023 These websites were created
during my teaching position at Flensburg University