Every other comparison sort on this site decides what to do next from the data: quicksort's next partition depends on where the pivot landed, insertion sort's inner loop runs until it hits a value that's already small enough, merge sort's merge step reads whichever side has the smaller head. Bitonic sort decides nothing from the data at all — the exact sequence of compare-exchange operations, and their order, is computed entirely from the array's length before a single element is ever inspected. Two arrays of the same size run through the identical sequence of index pairs no matter what values they hold; only whether each comparison triggers a swap depends on the data. This is what makes it a sorting network: a fixed circuit of comparators, the kind of algorithm that can be built directly in hardware or run identically across every lane of a GPU, where a data-dependent branch would force different lanes down different paths and destroy the parallelism.
Enter a comma-separated array of any length and step through. Bitonic sort's recursive
structure needs a power-of-two length at every level, so an array whose length isn't already a
power of two is padded with +∞ sentinel values first (dimmed bars, labeled
∞) — they behave like ordinary values in every comparison, they're just
guaranteed larger than anything real, so they settle at the very end. The demo leaves them visible
and dimmed past the real elements so you can see exactly where they land; the reference
implementation below drops them from its actual return value. The dashed box marks the current
bitonic block; the solid accent bar and the outlined bar are the two indices being compared right
now. Watch the comparator count at the default length (8, already a power of two) — then try a
random shuffle of the same eight values and confirm the count doesn't move.
A bitonic sequence is one that increases then decreases (or the reverse) —
it rises to a single peak (or falls to a single valley) at most once. The whole algorithm rests on
one fact about bitonic sequences: if you split one in half and compare-exchange each element in
the first half against its partner exactly len/2 positions ahead — forcing the
smaller of each pair into a chosen half — you get two new bitonic sequences, and every
element in one is now ≤ every element in the other. Repeat that halving-and-comparing step
(a bitonic merge) recursively on each half, and the whole thing untangles into
sorted order in log&sub2; n rounds.
That leaves one gap: a merge only works on a sequence that's already bitonic, and an
arbitrary input array isn't one. The fix is recursive in the other direction too: sort the left
half ascending and the right half descending (each by the same process, one level smaller), and
the concatenation of an ascending run followed by a descending run is bitonic by construction —
exactly the shape a merge needs. So bitonicSort on a block of size n
is "sort left half up, sort right half down, then bitonic-merge the whole block" — and
"sort half down" is the same procedure with the comparison direction flipped. Every comparator in
the whole network is decided purely by which recursive call it's inside and at what depth, never
by anything the array happens to contain.
Padding happens once, up front; everything below operates on the padded, power-of-two-length array in place:
function nextPow2(n) { let p = 1; while (p < n) p *= 2; return p; }
function bitonicSort(input) {
const n = input.length;
if (n <= 1) return input.slice();
const padded = nextPow2(n);
const arr = input.slice();
for (let i = n; i < padded; i++) arr.push(Infinity); // sentinel: always sorts last
sortBlock(arr, 0, padded, true);
return arr.slice(0, n); // trim the sentinels back off
}
function sortBlock(arr, lo, cnt, ascending) {
if (cnt <= 1) return;
const half = cnt / 2;
sortBlock(arr, lo, half, true); // left half: ascending
sortBlock(arr, lo + half, half, false); // right half: descending — together, bitonic
merge(arr, lo, cnt, ascending);
}
function merge(arr, lo, cnt, ascending) {
if (cnt <= 1) return;
const half = cnt / 2;
for (let i = lo; i < lo + half; i++) {
if ((arr[i] > arr[i + half]) === ascending) {
const t = arr[i]; arr[i] = arr[i + half]; arr[i + half] = t;
}
}
merge(arr, lo, half, ascending);
merge(arr, lo + half, half, ascending);
}Every comparator the algorithm ever runs is one line: (arr[i] > arr[i + half]) ===
ascending, called at index pairs that sortBlock/merge compute
purely from lo, cnt, and half — none of which depend on
arr's contents.
Skipping the padding step on a non-power-of-two length doesn't crash — it silently
sorts wrong almost every time. JavaScript doesn't complain about cnt / 2
producing a fractional half or an out-of-range index; the loops just run with the wrong bounds.
Running the unpadded version directly on every length from 2 to 40 that isn't a power of
two, 100 random trials each (3,400 trials total): 99.5% came back wrong, with
zero crashes or thrown errors the entire time — a silent-failure shape, not a loud one.
The padding value has to be provably larger than every real element, not just
"probably big enough." Padding with 0 instead of +∞ looks
harmless until the real array contains a negative number smaller than the pad — then the pad
value is no longer guaranteed to sort last, and it lands somewhere in the middle of the trimmed
output instead, silently displacing a real element. Tested against 2,000 random arrays of length
5–14 (guaranteed non-power-of-two, values including negatives) padded with 0:
79.5% came back wrong. +Infinity has no such failure mode — it
compares larger than any finite JavaScript number by definition, so it's always safe regardless of
the input's own range.
Forgetting to flip the direction on the second recursive half breaks the very shape
the merge step depends on. If sortBlock's right-hand recursive call is left
at ascending instead of switched to descending, the two halves are no
longer a rising run followed by a falling one — the concatenation isn't bitonic, and the merge
step's core guarantee (each compare-exchange separates into two cleanly bitonic halves) no longer
holds. Measured across 2,000 trials at sizes 4, 8, 16, and 32: 91.0% came back
wrong. The bug is one boolean literal, and every comparator still runs — nothing about the
network's shape looks wrong from the outside, it just stops proving anything about the result.
The comparator count really is fixed by length alone — checked, not just claimed.
Running the algorithm on a sorted array, a reverse-sorted array, and a random shuffle, all of the
same length, and counting every compare-exchange call: at n = 8 all three used
exactly 24 comparators; at n = 16, exactly 80; at
n = 32, exactly 240 — not "close," identical every time, matching the
closed form (n/4)·log&sub2;n·(log&sub2;n + 1) exactly at every size
tested. Contrast that with insertion
sort, whose whole appeal is the opposite property — its comparison count actively
depends on how sorted the input already is.
Time: O(n log² n) total comparators — worse than every other
comparison sort on this site, which all reach O(n log n) or better on average. That's
the honest tradeoff: bitonic sort spends extra total work to buy a property none of the others
have, a fixed, data-independent execution schedule. Parallel depth:
O(log² n) sequential rounds, but every comparator within a round touches
a disjoint pair of indices — all n/2 of them can run simultaneously on hardware with
that much parallelism, which is the entire reason this shape exists. Space:
O(n) for the padded array (up to just under double the input's own size, at worst
one element over a power of two) plus O(log n) recursion stack.
Bitonic sort doesn't compete in the small-n / stability / worst-case-guarantee funnel the other ten comparison sorts on this site answer — see Choosing a Comparison Sort for where it fits instead, and how its comparator count against the other ten, live in your own browser.