Here is my Radix Sort class that I've written.

The Radix sort (Sorts Least Significant Byte 1st) is a O( N ) bin sort. It is temporally coherent, independant of the data to sort, no worse case scenarios. However it requires extra memory.

It can handles the following data types: longword, longint & single. However it does not support arbitary data length. Changing the sorted data length shouldnt be too hard(but it has to be fixed)

How I've implemented it is O( k*N ), k=1,2-5 (k=1 when data is sorted, k=2-5 depending how how ordered the bytes are). Depending on the sort type (it supports actually outputing the sorted data to a seperate buffer or generating a list of indices which sort the data) it require O( N ) or O( 2*N ) extra memory.

Included is a quicksort implementation which is used to verify the integrity of the sort and as a time comparison. Only with ultra small data sets does quicksort beat radix sort.

At some point I'll make a post explaining the theory behind it.

Linky