bitonic sort

(algorithm)

Definition: Compare, and swap if necessary, pairs of elements in parallel. Subsets are sorted then merged.

Also known as Batcher sort.

Note: This takes O((log n)²/2) stages (or steps) with n/2 comparators at each stage.

This sorts increasingly larger intermingled subsets, somewhat like Shell sort, and merges subsets, like merge sort.

Elements are compared and swapped in a fixed (oblivious) schedule, so this may be implemented with only conditional swaps. Here is a Batcher sort for four elements:
compareAndSwap(0, 1);
compareAndSwap(2, 3);
compareAndSwap(0, 2);
compareAndSwap(1, 3);
compareAndSwap(1, 2);
where compareAndSwap(i,j) is if (a[i] < a[j]) Swap(a[i], a[j]).

This is Knuth's Algorithm M [Knuth98, 3:111, Sect. 5.2.2].

Author: PEB

Implementation

explanation, analysis, bibliography, etc. (Java). reference source code (C). Section from 1994 User Manual for Portable Parallel C++ (pC++).

More information

K. E. Batcher, Sorting Networks and their Applications, Proc. AFIPS Spring Joint Computer Conference, 32:307-314, 1968.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified Mon Nov 28 07:09:31 2005.
HTML page formatted Mon Nov 28 07:30:55 2005.

Cite this as:
Paul E. Black, "bitonic sort", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.
http://www.nist.gov/dads/HTML/bitonicSort.html