codersnotes

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[])
{
	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:

• Example source code

© 2022 Richard Mitton. All rights reserved.