# 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]). Notice that the first pair of operations, (0, 1) and (2, 3), can be performed in parallel, as can the second pair (0, 2) and (1, 3).
* Knuth calls this Algorithm 5.2.2M [Knuth98, 3:111].*

Author: PEB

## Implementation

explanation, analysis, bibliography, etc. (Java). Other implementations in (C) and in (Java).
## 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 Black.

Entry modified 25 March 2014.

HTML page formatted Fri Feb 23 10:06:07 2018.

Cite this as:

Paul E. Black, "bitonic sort", in
*Dictionary of Algorithms and Data Structures* [online], Vreda Pieterse and Paul E. Black, eds. 25 March 2014. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/bitonicSort.html