Linked-list radix sort February 14th, 2009

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 performance 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.
Note: I've used a template parameter for the shift value, as the architecture I'm working on doesn't like variable-length shifts. You could probably just replace that with a normal function variable instead.
template<int shift>
Sortable *rsorti(Sortable *head, Sortable lists[], Sortable *tails[])
		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; }

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; }
Here's the full source code for this article:

Written by Richard Mitton,

software engineer and travelling wizard.

Follow me on twitter: