Linked-List Radix Sort

Here's a small snippet to show how you can sort a linked-list using radix sort.

Radix sort isn't a comparison-based sort, which means it can attain O(n) performance. However if you're sorting a flat array, it has to do a lot of data shuffling. This is one of the few times where a linked-list actually has a peformance advantage, as it can shuffle the lists around with only a single re-link operation.

This code assumes you've got a base class called 'Sortable', which you inherit from. 


struct Sortable
{
	u32 sortKey;
	Sortable *next;
};

sortKey is a 32-bit integer which will be used to define the sort order. You could also sort (non-negative) floats using the same method, by using a union here.

On my tests, this code beats both libc qsort and stl::sort. stl::sort might be able to beat it on small lists; this is really designed for sorting at least 100 objects. 


template<int shift>
Sortable *rsorti(Sortable *head, Sortable lists[], Sortable *tails[])
{
	while(head)
	{
		u32 bucket = (head->sortKey >> shift) & 0xff;

		tails[bucket]->next = head;
		tails[bucket] = head;
		head = head->next;
	}

	Sortable list;
	Sortable *prev = &list;
	for (unsigned int n=0;n<256;n++)
	{
		if (lists[n].next)
		{
			prev->next = lists[n].next;
			prev = tails[n];
			lists[n].next = NULL;
			tails[n] = &lists[n];
		}
	}
	prev->next = NULL;
	return list.next;
}

template<typename T>
T *rsort(T *head)
{
	Sortable lists[256];
	Sortable *tails[256];

	if (!head)
		return NULL;

	for (unsigned int n=0;n<256;n++)
	{
		lists[n].next = NULL;
		tails[n] = &lists[n];
	}

	Sortable *sorted = head;
	sorted = rsorti<0>(sorted, lists, tails);
	sorted = rsorti<8>(sorted, lists, tails);
	sorted = rsorti<16>(sorted, lists, tails);
	sorted = rsorti<24>(sorted, lists, tails);
	return (T *)sorted;
}
example source - rsort.zip