Radix Sort Working

Question

i wanted to know the logic of following radix sort program.

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

typedef unsigned uint;
#define swap(a, b) { tmp = a; a = b; b = tmp; }
#define each(i, x) for (i = 0; i < x; i++)

/* sort unsigned ints */
static void rad_sort_u(uint *from, uint *to, uint bit)
{
    if (!bit || to < from + 1) return;

uint *ll = from, *rr = to - 1, tmp;
while (1) {
    /* find left most with bit, and right most without bit, swap */
    while (ll < rr && !(*ll & bit)) ll++;
    while (ll < rr &&  (*rr & bit)) rr--;
    if (ll >= rr) break;
    swap(*ll, *rr);
}

if (!(bit & *ll) && ll < to) ll++;
bit >>= 1;

rad_sort_u(from, ll, bit);
rad_sort_u(ll, to, bit);
}

/* sort signed ints: flip highest bit, sort as unsigned, flip back */
static void radix_sort(int *a, const size_t len)
{
size_t i;
uint *x = (uint*) a;

each(i, len) x[i] ^= INT_MIN;
rad_sort_u(x, x + len, INT_MIN);
each(i, len) x[i] ^= INT_MIN;
}

static inline void radix_sort_unsigned(uint *a, const size_t len)
{
rad_sort_u(a, a + len, (uint)INT_MIN);
}

int main(void)
{
int len = 16, x[16], i;
size_t len = 16, i;
each(i, len) x[i] = rand() % 512 - 256;

radix_sort(x, len);

each(i, len) printf("%d%c", x[i], i + 1 < len ? ' ' : '\n');

return 0;
}

i am stuck because i dont quite understand the while(1) loop..

so far what i have come to know is :

INT_MIN=-2147483648

this is same as value of bit in rad_short_u()

i had debugged the program, due to rand() % 512-256, some -ve values are also generated,

during first pass it swaps all -ve values to one side(from starting) and +ve after that from next pass it shifts left to 1 bit so bit's value becomes 1073741824 from then to until it becomes 1 array remains same.

please help me to understand the program logic.

Answer 1

To understand this program, you need to understand both quicksort and most-significant-bit radix sort.

Like quicksort, it partitions the array into parts, then recursively sorts the parts. It first partitions based on the value of the most significant bit. Then it recurses on both halves. But this time, for each half, it partitions based on the second most significant bit. Then it divides again, and for each 1/4, it partitions on the 3rd most significant bit...

Note that while I am saying "1/2", "1/4", and so on, it will not typically divide the array into exactly 1/2, 1/4, etc. The size of each division will depend on the distribution of numbers in the array. For a normal quicksort, the size of each division would depend on the element chosen as "pivot", but that is not true for this "radix quicksort" -- the sequence of "pivots" is fixed.

Note, also, that unlike a normal quicksort, which can go quadratic and become very slow on certain inputs, this "quicksort" is guaranteed to finish in a fixed number of passes. Actually, the number of passes required is a constant, no matter the input. (This is a typical property of radix sorts -- performance tends to be insensitive to the input.)

Another interesting property: a normal quicksort would divide the array into 3 parts -- those lesser, equal, and greater than the pivot. But this "quicksort" always divides its input into exactly 2 parts on each pass -- those with a 0 bit in the position being tested, and those with a 1 bit.

I think the name of this algorithm is actually "binary quicksort".