RadixSort : Java Glossary

	recommend book⇒The Art of Computer Programming
		hardcover
	ISBN13:	978-0-201-48541-7
	ISBN10:	0-201-48541-9
	publisher:	Addison-Wesley
	published:	1998-10-15
	by:	Donald Knuth
Knuth’s volumes 1, 2 and 3 are the reference works for standard algorithms. At his website he describes plans for volumes 4 and 5.
abe books.co.uk abe books.ca amazon.co.uk amazon.ca abe books.de chapters.indigo.ca amazon.de abe books.com abe books.fr amazon.com amazon.fr barnes and noble.com abe books.it powells.com iberlibro.com abe books anz

The radix-distribution sort (which I call here simply RadixSort) is discussed at length in Knuth’s Art of Computer Programming vol 3 #5.2.5, where he says that it was first published in 1929 in connection with tabulating machines, although it was probably known to the operators before that, and first described in the form included here in 1954. There is also a related radix-exchange sort.

Advantages

RadixSort is stable, meaning it preserves existing order of equal keys. It works in linear time, unlike most other sorts. In other words, it does not bog down when you have large numbers of items to sort. The time per item to sort is constant. With other sorts, the time to sort per time increases with the number of items. Mathematicians would put it that most sorts run in O(n log(n)) or O(n²) time, where RadixSort runs in O(n) time.

Drawbacks

• RadixSort does not work well when you have very long keys, because the total sorting time is proportional to key length and to the number of items to sort. If you insisted that all records have unique keys, necessarily the keys would have to be at least log₂(n) bits long, which would tend to defeat the advantage of RadixSort. RadixSort shines when you have large numbers of records to sort with short keys.
• Unfortunately, in this particular implementation, 16 bit characters count as two key slots, unless you can guarantee you never user the high order parts. In other words Unicode takes twice as long to sort as byte arrays
• The biggest drawback with RadixSort is that you have to write an unconventional compare routine.
• The other drawback is RadixSort also uses somewhat more working storage than a traditional sort, because it copies references to the elements to sort back and forth between two arrays for each pass. Many other sorts make do with one array and some stack space.

Tuning

Since all sorts can use the same Comparator interface, it is possible to experiment with various sorts to figure out which one works best for your situation.

Variants