RadixSort

Marks the ranks as stale, so rank and reorder refuse to use them until the next sort. The tables are kept.

Makes the rank tables hold new_size entries, allocating if they must grow, and marks the ranks as stale. sort calls this for you; call it first to allocate ahead of time.

Frees the rank tables and clears the ranks. The sorter can be used again afterwards, allocating anew.

The index in the sorted input of the i-th smallest element. Fails an assert when no sort has produced valid ranks or i is out of range.

Ranks count numbers at input from smallest to largest, or all of an array view; supports u32, u64 and float.

sorter: RadixSort;
values := float.[2.5, -1, 9, 0];
sort(*sorter, values);

smallest := values[rank(*sorter, 0)];
largest := values[rank(*sorter, 3)];
assert(smallest == -1 && largest == 9);
free_resources(*sorter);

Rearranges a dynamic array into sorted order, using the ranks of the last sort of that array.

values: [..] u64;
array_add(*values, 30, 10, 20);

sorter: RadixSort;
sort(*sorter, values);
reorder(*values, sorter);
assert(values[0] == 10 && values[1] == 20 && values[2] == 30);

free_resources(*sorter);
array_free(values);

A built-in smoke test that sorts three numbers and asserts the ranks. It is not part of the sorting API.

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

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);