C++ Radix Sort with bitwise operations [duplicate]

Question

This question already has an answer here:

Radix sort using bitwise operations (1 answer)

Closed 8 years ago.

I'm trying to understand how radix sort works with bitwise , so i found this algorithm in the internet but i couldn't understand how it works !

#include <algorithm>
#include <iostream>
#include <iterator>

// Radix sort comparator for 32-bit two's complement integers
class radix_test
{
    const int bit; // bit position [0..31] to examine
public:
    radix_test(int offset) : bit(offset) {} // constructor

    bool operator()(int value) const // function call operator
    {
        if (bit == 31) // sign bit
            return value < 0; // negative int to left partition
        else
            return !(value & (1 << bit)); // 0 bit to left partition
    }
};

// Least significant digit radix sort
void lsd_radix_sort(int *first, int *last)
{
    for (int lsb = 0; lsb < 32; ++lsb) // least-significant-bit
    {
        std::stable_partition(first, last, radix_test(lsb));
    }
}

// Most significant digit radix sort (recursive)
void msd_radix_sort(int *first, int *last, int msb = 31)
{
    if (first != last && msb >= 0)
    {
        int *mid = std::partition(first, last, radix_test(msb));
        msb--; // decrement most-significant-bit
        msd_radix_sort(first, mid, msb); // sort left partition
        msd_radix_sort(mid, last, msb); // sort right partition
    }
}

// test radix_sort
int main()
{
    int data[] = { 170, 45, 75, -90, -802, 24, 2, 66 };

    lsd_radix_sort(data, data + 8);
    // msd_radix_sort(data, data + 8);

    std::copy(data, data + 8, std::ostream_iterator<int>(std::cout, " "));

    return 0;
}

Can any one please explain how this work to sort integers ! Thanks so much

Answer 1

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.