Well, you say you understand how a MSD radix sort works, so in that case, the key parts are:
class radix_test {
bool operator()(int value) const // function call operator
{
...
return !(value & (1 << bit)); // 0 bit to left partition
}
}
The radix_test
is a functionoid that when given a value and a bit number, tests if that bit is not set in the given value. 1<<bit
results in a bitmask for that bit number, and then value & <bitmask>
results in <bitmask>
if the bit is set, or 0
otherwise. Then the person uses !
to return true if the bit is NOT set.
void msd_radix_sort(... int msb = 31)
{
if (.... msb >= 0)
{
... std::partition(... radix_test(msb));
msb--; // decrement most-significant-bit
msd_radix_sort(..., msb); // sort left partition
msd_radix_sort(..., msb); // sort right partition
}
}
The sort itself starts with the 32nd bit (bit ID 31), and uses std::partition
to put all the values with that bit not set on the left, and the values where that bit is set on the right. Then it recurses on the two halves with the next smaller bit. By the time it hits the end, the data is sorted.
Since this implementation works on the single-bit-level (thus base 2), this is effectively a quicksort. radix sorts can really shine when you alter them to work with more groups (not in-place), but it's highly dependent on the types and amounts of data. With four billion integers that use the full range of values I'd probably use 524288 buckets instead of two, and then instead of recursing down, simply switch to a introsort.