Task 3 of 5

Which Way Does My Pair Sort?

Every pass so far sorted every pair the same way. A bitonic network does not, and that is the whole trick. A sequence that rises and then falls is called bitonic, and a bitonic sequence is the one thing this network can merge into sorted order in log n passes. So the early passes exist to build bitonic runs: neighbouring blocks are deliberately sorted in opposite directions, so that gluing two of them together gives up then down.

Which way your block goes is another bit of your index — the one named by stage, the size of the block currently being merged:

const dirBit = Math.floor(i / stage) % 2;   // 0 → my block sorts ascending

So a thread now holds two bits. strideBit says whether it is the low or the high member of its pair; dirBit says which way its block is sorting. And the rule is as small as it could be: keep the smaller value exactly when the two bits agree. Low member of an ascending block, or high member of a descending one — either way, minimum.

One detail makes that legal: stride is always smaller than stage, so flipping the stride bit never disturbs the direction bit. Both members of a pair read the same dirBit and agree about which way they are sorting — without exchanging a word.

neighbouring blocks sort opposite ways, and your index already knows which

Goal: write one full bitonic pass over 8 values — the kernel takes (data, stage, stride) and returns each thread's new value.

Requirements

Compute both bits: strideBit from stride, dirBit from stage
The partner still comes from strideBit, exactly as in the last task
Return Math.min when the two bits agree and Math.max when they differ

Hint 1 — reading the rule off the table

Four cases, and they collapse to one comparison:

low  + ascending  → min      (0, 0) agree
high + ascending  → max      (1, 0) differ
low  + descending → max      (0, 1) differ
high + descending → min      (1, 1) agree

Hint 2 — the whole body

const i = this.thread.x;
const strideBit = Math.floor(i / stride) % 2;
const dirBit = Math.floor(i / stage) % 2;

let partner = i - stride;
if (strideBit === 0) partner = i + stride;

const me = data[i];
const other = data[partner];
if (strideBit === dirBit) return Math.min(me, other);
return Math.max(me, other);

Same idea elsewhere

Every bitonic implementation on every platform carries this pair of bit tests — CUDA samples write (i & k) == 0, WGSL compute shaders write the same thing with &, and the arithmetic spelling here says exactly the same. What none of them need is communication: the direction is a property of your index, so a thread can work it out alone, which is what makes the whole network barrier-free within a pass.

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.