If you have a short key or a huge data set, counting sort will probably be fastest. For enormous data sets, Counting sort will always be faster for some large n. If you have only one or two bits in your key, you might use Radix sort instead of counting sort. Besides, it is so simple that it will fit most insctruction caches. Technique is basically a mergesort, where traversal to the second sublist is done on the fly while sorting the first sublist.
Details are in the code.
Otherwise include listsort.c itself. It is small enough. The problem with these sorts is that it is extremely difficult to write an efficient, general-purpose radix sort, and even when you have, it still isn't faster than quicksort unless you have enormous arrays to sort. If so, I'd like to see your algorithm. Giaimo Remove nospam.