Task 6 of 6

Keys That Aren't Plain Integers

The sort has a requirement it never had to say out loud: the key must be a non-negative integer, because Math.floor(key / place) % 16 is only a digit for those. Hand it −5 and the "digit" is −5, starts[−5] is off the front of the bucket table, and the pass returns junk.

Signed integers have a clean fix that costs one map each way: bias them. Add 2,048 and the range −2048…2047 becomes 0…4095 — same order, all non-negative. Sort, then subtract the 2,048 back off. Production libraries call this step encoding the key, and the rule is the only one that matters: any order-preserving, invertible map into the unsigned integers makes radix sort work on your type.

Floats are the same idea and a harder map — and this is where gpu.js stops. A float's ordering is its bit pattern's ordering, for positives; IEEE-754 negatives carry a sign bit on top and sort backwards under an unsigned comparison, so real implementations reinterpret the 32 bits and flip them (x ^ 0x80000000 for a positive, ~x for a negative) before sorting and flip back after. gpu.js does have &, |, ^, << and >> inside kernels, but the WebGL backend emulates them with GLSL integer loops and they part company with JavaScript the moment an operand goes negative (-8 & 15 is 8 in JavaScript and on the CPU backend, and 0 on WebGL). More to the point, there is no way to see a float's bits at all: GLSL ES 1.00 has no floatBitsToInt and gpu.js exposes none, so key & 15 truncates the value to an integer first — 3.5 & 15 is 3, the number's integer part, never its bit pattern. This course therefore sorts non-negative integer keys, and signed ones through the bias below; a CUDA or WebGPU implementation runs the same six kernels with a bit-flipping encoder in front.

Goal: sort readings, which run from −2048 to 2047, by biasing them into non-negative integers, sorting, and taking the bias back off.

Requirements

encode adds this.constants.bias to every reading
decode subtracts it again
Run the given radixSort on the encoded values, and decode the result
console.log the sorted readings' smallest and largest values

Hint 1 — the two maps

Both kernels are one-line maps over their own cell — one adds this.constants.bias, the other subtracts it. Nothing about the sort changes.

Hint 2 — the wiring

const sorted = await decode(await radixSort(await encode(readings)));

Encode on the way in, decode on the way out. Miss the decode and every value comes back 2,048 too high; miss the encode and the negative keys index off the front of the bucket table.

Same idea elsewhere

Every serious sorting library has this seam. CUB twiddles a key's bits in and out around the sort so that floats, signed integers and custom types all reduce to unsigned digits; rocPRIM and Thrust do the same, and newer CUB versions let you hand it a decomposer for your own struct. The sort never changes — only the map into unsigned integers does.

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.