NIST

bitonic sort

(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);
     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]).

Knuth calls this Algorithm 5.2.2M [Knuth98, 3:111].

Author: PEB

Implementation

explanation, analysis, bibliography, etc. (Java). reference source code (C) and in (Java). 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 4 September 2009.
HTML page formatted Fri Sep 4 11:48:36 2009.

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. 4 September 2009. (accessed TODAY) Available from: http://www.itl.nist.gov/div897/sqg/dads/HTML/bitonicSort.html

to NIST home page