Task 4 of 6

Whose Value Lands Here?

Everything so far produced a plan: for each element, the slot it belongs in. Executing the plan is the one move a kernel does not have. out[destinations[i]] = keys[i] is a scatter — a thread writing somewhere other than its own cell — and gpu.js has no such thing (Thinking in Parallel makes a whole module of why).

So turn the question round, exactly as you would anywhere else on a GPU. Instead of "where does my value go?", output slot x asks "which element wants me?" — sweep the destinations, find the one that equals x, and take that element's key. Every thread reads the whole plan and writes one cell. It looks wasteful and it is completely parallel, which on a GPU is the trade you take.

Goal: apply the permutation with a gather — output slot x holds the key of the element whose destination is x.

Requirements

Hint 1 — which comparison?

destinations[i] is where element i is going. Your cell is this.thread.x. So the element you want is the one where those two are equal — never keys[destinations[this.thread.x]], which applies the permutation backwards.

Hint 2 — the sweep
let value = 0;
for (let i = 0; i < this.constants.n; i++) {
  if (destinations[i] === this.thread.x) {
    value = keys[i];
  }
}
return value;

Same idea elsewhere

Compute APIs do let you scatter — CUDA and WebGPU threads can store to any buffer address — and a production radix sort uses that: it writes keys straight to their computed offsets, which is why it also needs atomics and shared memory to arrange those offsets safely. Where you have no scatter, the inversion here is the standard replacement, and it is the same move a fragment shader has made since the beginning: every output pixel pulls what it needs.

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.