C/C++: Radix Sort Algorithm

Radix sort appears to sort numbers very well indeed; however, it does not seem applicable to strings. Plus, quick sort out performs it. See the Algorithm Study for comparisons.

// more or less, the original algorithm as posted on Wikipedia
class CRadixSort
{
private:
	CRadixSort(){;}
	static void rad_sort_u(unsigned int *from, unsigned int *to, unsigned int bit)
	{
		if (!bit || to < from + 1) return;
 
		unsigned int *ll = from, *rr = to - 1, tmp;
		while (1) {
			while (ll < rr && !(*ll & bit)) ll++;
			while (ll < rr &&	(*rr & bit)) rr--;
			if (ll >= rr) break;
			tmp = *ll;
			*ll = *rr;
			*rr = tmp;
		}
 
		if (!(bit & *ll) && ll < to) ll++;
		bit >>= 1;
 
		rad_sort_u(from, ll, bit);
		rad_sort_u(ll, to, bit);
	}
public: 
	static void radix_sort(int *array, const unsigned int len)
	{
		unsigned int i, *x = (unsigned int*)array;
 
		for(i = 0; i < len; i++)
			x[i] ^= -2147483648;
		rad_sort_u(x, x + len, -2147483648);
		for(i = 0; i < len; i++)
			x[i] ^= -2147483648;
	}
 
	static void radix_sort_unsigned(unsigned int *array, const unsigned int len)
	{
		rad_sort_u(array, array + len, (unsigned int)-2147483648);
	}
};

Comment