Task 1 of 6

Sort by One Digit

Radix sort never compares two keys. It sorts by one digit at a time, starting with the least significant, and after enough passes the array is sorted — which reads like a card trick until you watch it happen:

  start    by ones    by tens
    34        21         13
    21        13         21  ← tie
    13        34         27  ← tie
    27        27         34

The tens pass never looks at the ones digit. All it knows is that 21 and 27 both have a 2 — and the only reason 21 still comes out first is that the pass is stable: it leaves equal digits in the order it found them, and the ones pass had already put 21 first. Break that and the earlier pass's work is destroyed. An unstable tens pass may emit 13, 27, 21, 34: perfectly ordered by tens digit, and not sorted.

So each pass has to answer one question per element: how many elements belong in front of me? Everything with a smaller digit, plus everything with the same digit that started earlier. That second clause is stability.

equal digits keep the order they arrived in — cross those arrows and the previous pass was wasted

Goal: for every element of digits, return the index it lands on in a stable one-digit pass.

Requirements

Loop over all this.constants.n digits — one pass over the array per thread
Count every digit strictly smaller than yours
Break ties by original position: count an equal digit only when its index is before this.thread.x
Return the count — that count is the destination

Hint 1 — two counts, one loop

Walk every j from 0 to n − 1 and ask two questions about digits[j]: is it smaller than mine? and if it is equal to mine, did it start before me? Either one puts that element in front of you.

Hint 2 — the tie-break

const other = digits[j];
if (other < mine) {
  before++;
} else if (other === mine && j < this.thread.x) {
  before++;
}

The j < this.thread.x is the entire stability guarantee. Turn it round and the pass still sorts by digit — and still destroys everything the previous pass did.

Same idea elsewhere

Every production GPU radix sort is a stable sort, and not by accident: NVIDIA's CUB ranks each key inside its digit with BlockRadixRank, AMD's rocPRIM and Metal's sort primitives do the same. Stability is what makes multi-pass radix sorting work at all, and it is also what lets you sort key–value pairs, or sort by one field and then another, and trust the result.

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.