## 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 theshiftvalue, 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[]) { while(head) { u32 bucket = (head->sortKey >> shift) & 0xff;Here's the full source code for this article:

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; }

### Written by Richard Mitton,

software engineer and travelling wizard.

Follow me on twitter: http://twitter.com/grumpygiant