radix_scatter

Stage 3 of one pass of the shared GPU radix sort. One workgroup of 256 per 256 items, once per radix pass.

Each thread extracts its item's digit for this pass and counts how many earlier threads in its own block carry the same digit. That rank, added to the scanned histogram entry for (digit, block), is the item's slot in the output permutation.

The rank is a count over a fixed range of workgroup memory, so it depends on nothing but the block's own keys: two runs over the same keys place every item in the same slot. Items sharing a digit keep their relative order from the input permutation, which makes the pass stable and the whole multi-pass sort a total order on (key, item index) — one permutation, reachable from the keys alone.

On the last pass an item whose key reaches sort[4] resolves to 0xffffffff instead of its index. Such an item carries a key past the last real one, so it occupies the tail of the permutation, and the consumer reads 0xffffffff as "this slot draws nothing".

Bindings

Slot	Access	Contents
keys	read	Per-item sort key.
indices_in	read	This pass's input permutation.
indices_out	read_write	This pass's output permutation.
hist	read	Scanned digit histogram from radix_scan.
sort	read	[0] count, [1] blocks, [2] shift, [3] last-pass flag, [4] dropped key.

Dispatch one workgroup of 256 per 256 items.