# Sort by One Digit

*Task 1 of 6 · [Radix Sort](https://gpu.rocks/learn/radix-sort-fd3ff796.md) · GPU.js Learn*

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:

```js
  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.

## Figures

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

## Goal

**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

```js
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.

## Starter code

```js
// A stable pass answers one question per element:
// how many elements belong in front of me?
const gpu = new GPU({ mode });

const destination = gpu.createKernel(function (digits) {
  const mine = digits[this.thread.x];
  let before = 0;
  for (let j = 0; j < this.constants.n; j++) {
    // TODO: count the digits that belong in front of this one —
    // everything smaller, plus the EQUAL digits that started earlier.
    if (digits[j] < mine) {
      before++;
    }
  }
  return before;
}, {
  output: [16],
  constants: { n: 16 },
});

const dest = await destination(digits);
console.log('digits:      ', digits.join(' '));
console.log('destinations:', Array.from(dest).join(' '));
```

---

Interactive version: https://gpu.rocks/learn/radix-sort-fd3ff796/1

[Next task](https://gpu.rocks/learn/radix-sort-fd3ff796/2.md)