twitter:
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.
{
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.
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;
}
Here’s the full source code for this article:
rsort.cpp
[1.91KB] - example source code
