Task 4 of 5

Drive the Whole Network

One pass is one kernel launch. The network is two plain JavaScript loops around it — stages doubling outward, and within each stage strides halving down to 1. Here is the thing worth noticing, though: those loops never look at the data. So don't interleave them with it. Build the entire schedule first, as a list of [stage, stride] pairs, and print it:

const schedule = [];
for (let stage = 2; stage <= n; stage *= 2) {
  for (let stride = stage / 2; stride >= 1; stride /= 2) {
    schedule.push([stage, stride]);
  }
}

All 36 pairs for n = 256, complete, before a single value has been read. Then run them. That is the property this whole module is about: every thread derives its partner and its direction from its own index, so nothing waits on a comparison, no warp diverges, and nobody has to be told anything. A quicksort cannot do this — you do not know its second partition until you have done the first.

The bill comes due in comparisons. Bitonic sort does O(n log²n) of them where quicksort does O(n log n): 36 passes × 128 pairs = 4,608 compare-exchanges for 256 values, against roughly 2,000. More than twice the work — in 36 sequential steps, with everything inside a step happening at once. That trade, a predictable structure bought with extra work, is the most transferable idea in this course.

six passes, twenty-four comparators, and not one of them depends on a value

Goal: build and print the whole 36-pass schedule before touching the data, run it to sort 256 values, and log the smallest and largest of the result.

Requirements

schedule holds the [stage, stride] pairs: stages doubling from 2 up to and including n, strides halving from stage / 2 down to 1
Build it without reading data — the schedule is complete before the first kernel call
console.log the pass count and the schedule itself (already wired up)
console.log the smallest and largest values of the sorted result

Hint 1 — the two loops

Outer loop doubles, inner loop halves, and both bounds are inclusive at the far end: stage <= n, stride >= 1. The body is one line — schedule.push([stage, stride]);

Hint 2 — the last stage is the one that sorts

Stopping at stage < n costs exactly one merge, and that merge is the one that turns a bitonic sequence into a sorted array. The result looks plausible — it rises, then falls — and it is wrong.

Hint 3 — the first few pairs

A correct schedule starts

[[2,1], [4,2], [4,1], [8,4], [8,2], [8,1], [16,8], …]

— stride 2 before stride 1 inside stage 4, not after.

Same idea elsewhere

A host-side loop issuing one kernel launch per pass is exactly how bitonic sort ships in practice: CUDA samples launch bitonicSortShared once per (stage, stride), WebGPU records one dispatch per pass into a command encoder, and Metal encodes one compute pass each. The launches are the synchronisation — everything within a pass is independent, and the boundary between passes is the only barrier anyone needs.

All tasks in Bitonic Sort

This page is an interactive exercise — the editor, the GPU runner and your saved progress need JavaScript. The text above is the full brief.