Task 2 of 6

One Bit at a Time

Take the narrowest radix there is: 2. One bit per pass, two buckets, and the whole bucket table collapses to a single number — how many zeros there are. Zeros go to the front in the order they appeared; ones go behind them, also in order. So element i's destination is either how many zeros are before me, or every zero, plus how many ones are before me.

That count of preceding flags is a running total over a 0/1 array — the same shape stream compaction uses to close its gaps, except here neither half gets thrown away. The zero total is 32 numbers coming back to JavaScript, which is cheap to finish there.

Moving the data is one line of ordinary JavaScript: out[dest[i]] = keys[i]. Enjoy it while it lasts. That line is a scatter, and it is the one thing a kernel cannot do — task 4 is about turning it inside out.

Goal: split keys by their low bit — even keys first, odd keys behind them, each half keeping its original order — and log the result.

Requirements

lowBit returns keys[this.thread.x] % 2 — a 0/1 flag per key
Count the zeros in plain JavaScript and pass the total into the second kernel
A zero's destination is how many zeros came before it; a one's is zeros plus how many ones came before it
console.log the reordered array (the starter's last line already does)

Hint 1 — count your own kind

Both halves need the same thing: how many earlier elements share your flag. One loop does it for either flag —

if (bits[j] === mine && j < this.thread.x) before++;

— and then only the starting point differs.

Hint 2 — the two starting points

The zero bucket starts at slot 0. The one bucket starts right after every zero, at slot zeros:

if (mine === 0) return before;
return zeros + before;

Same idea elsewhere

The one-bit split is where GPU radix sorting started — Satish, Harris and Garland's manycore sorting paper builds an entire sort from it, one bit at a time, with a prefix sum over the flag array supplying every destination. Modern hardware does the counting in a single instruction: CUDA's __ballot_sync + __popc and WGSL's subgroupBallot give a warp its flag ranks for free.

All tasks in Radix 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.