Task 3 of 6

Widen the Radix

One bit per pass means 32 passes for a 32-bit key. Four bits per pass means 16 buckets and eight passes — the same total work rearranged, with far fewer round trips. That is the real engineering trade in radix sorting, and every library picks a number here (4 and 8 bits are the usual answers).

The price is that the bucket table stops being a single number. You need a histogram — how many keys carry each of the 16 digits — and then a running total across the buckets to turn those counts into starting offsets: bucket b begins after every key whose digit is smaller than b. Both of those are primitives in their own right (and each has a module of its own); at 16 buckets they are small enough to write out in a loop.

Note the word smaller. The scan is exclusive: bucket 0 starts at slot 0, and bucket b's offset stops at b − 1. Include your own count and every bucket starts one whole bucket too far along.

count, scan, and every key knows its slot without comparing itself to anything (four buckets here, sixteen in the code)
Goal: write both kernels — histogram counts the keys in each of the 16 digit buckets at a given place, and offsets turns those counts into starting slots with an exclusive scan.

Requirements

Hint 1 — extracting a digit

place selects which digit you want: 1 for the ones digit, 16 for the sixteens, 256 for the next. Divide it away, then take what is left modulo the radix:

const d = Math.floor(keys[i] / place) % this.constants.radix;

Skip the % 16 and d is the whole quotient, not a digit.

Hint 2 — the histogram is a gather, not a scatter

You cannot walk the keys and bump a counter — that is 64 threads fighting over 16 cells. Invert it: each of the 16 threads owns one bucket and walks the whole key array counting its own digit. if (d === this.thread.x) count++;

Hint 3 — exclusive means stop early
for (let b = 0; b < this.constants.radix; b++) {
  if (b < this.thread.x) start += counts[b];
}

Sixteen values is far too few to be worth a clever scan; the point is the b < this.thread.x.

Same idea elsewhere

Count, scan, scatter is the skeleton of every real GPU radix sort: CUB and rocPRIM histogram each tile of keys locally, scan the per-tile histograms into global digit offsets, then move the keys. Choosing the radix is a genuine tuning knob — wider digits mean fewer passes over memory but a bigger bucket table to keep on chip, which is why 4 and 8 bits win in practice and 16 does not.

All tasks in Radix Sort

  1. Sort by One Digit
  2. One Bit at a Time
  3. Widen the Radix
  4. Whose Value Lands Here?
  5. The Whole Sort
  6. Keys That Aren't Plain Integers

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