(algorithm)
Definition: Compare, and swap if necessary, pairs of elements in parallel. Subsets are sorted then merged.
Also known as Batcher sort.
Generalization (I am a kind of ...)
oblivious algorithm.
Note: This takes O((log n)2/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);where compareAndSwap(i,j) is if (a[i] < a[j]) Swap(a[i], a[j]).
compareAndSwap(2, 3);
compareAndSwap(0, 2);
compareAndSwap(1, 3);
compareAndSwap(1, 2);
This is Knuth's Algorithm M [Knuth98, 3:111, Sect. 5.2.2].
Author: PEB
K. E. Batcher, Sorting Networks and their Applications, Proc. AFIPS Spring Joint Computer Conference, 32:307-314, 1968.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 14 August 2008.
HTML page formatted Thu Aug 14 12:18:07 2008.
Cite this as:
Paul E. Black, "bitonic sort", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 14 August 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/bitonicSort.html
