RadixSort

Scratch state for radix sorting, which orders the numbers in an array by their bytes rather than by comparing them.

sort does not move the input. It fills a table of ranks: after sorting, rank(*sorter, i) (also sorter[i]) is the index in the input of the element that belongs at position i. Use the ranks to read the input in order, or reorder to rearrange a dynamic array to match. The sort is stable, linear in the input size and needs one pass per byte of the element type, so it beats comparison sorts on large arrays of u32, u64 and float. Signed integers are not supported: convert them first.

The rank tables are allocated by sort (from allocator, or context.allocator when it is unset) and reused by later sorts of the same or a smaller size. Release them with free_resources.

sorter: RadixSort;
values := u32.[40, 7, 19];
sort(*sorter, values);
assert(sorter[0] == 1 && sorter[1] == 2 && sorter[2] == 0); // 7, 19, 40
free_resources(*sorter);