RadixSort : Java Glossary

*0-9ABCDEFGHIJKLMNOPQRSTUVWXYZ (all)

RadixSort
is a sorting technique that mimics the old card sorters that worked column by column sending punched cards into different bins. I first heard of the idea from the late Tom Meikle who was a novice programmer when he independently discovered it back in 1968 when we implemented it for the venerable LGP-30. He called it DigitSort. Only many years later after teaching it to scores of people did I learn it was already well known by the name RadixSort.
book cover recommend book⇒Origin Of Speciesto book home
by Charles Darwin 978-0-451-52906-0 paperback
birth 1809-02-12 died: 1882-04-19 at age: 73 978-0-679-60070-1 hardcover
publisher Signet Classics 978-0-679-64130-8 eBook
published 2003-09-02 978-1-4001-0215-0 audio
  B002JF1N0A kindle
This in one of the few books of the period that stand up to repeated readings today.
Australian flag abe books anz abe books.co.uk UK flag
Chinese flag amazon.cn amazon.co.uk UK flag
German flag abe books.de abe books.ca Canadian flag
German flag amazon.de amazon.ca Canadian flag
Spanish flag amazon.es Chapters Indigo Canadian flag
Spanish flag iberlibro.com abe books.com American flag
French flag abe books.fr amazon.com American flag
French flag amazon.fr Barnes & Noble American flag
Italian flag abe books.it Google play American flag
Italian flag amazon.it O’Reilly Safari American flag
India flag junglee.com Powells American flag
UN flag Kobo other stores UN flag
Greyed out stores probably do not have the item in stock. Try looking for it with a bookfinder.
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

In Java, RadixSort is faster than either QuickSort or HeapSort in the benchmarks I ran. For small numbers of items, almost any sorting algorithm will work just fine. There is rarely any reason to use anything but the built intournament sort, unless the sort is too big to fit in RAM (Random Access Memory), where you need something like opt-sort.

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

Tuning

If you want a high speed version of RadixSort for a particular application, you will have to inline the comparison delegate code since delegate.getKeyByteAt, is where it chews up all the CPU (Central Processing Unit) time.

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

There are other ways to implement the same basic algorithm by chaining the objects to be sorted together, but that tends to be inefficient in Java since you need separate glue objects to do the linking unless the items to be sorted themselves implement some chaining interface.

This page is posted
on the web at:

http://mindprod.com/jgloss/radixsort.html

Optional Replicator mirror
of mindprod.com
on local hard disk J:

J:\mindprod\jgloss\radixsort.html
logo
Please the feedback from other visitors, or your own feedback about the site.
Contact Roedy. Please feel free to link to this page without explicit permission.
no blog for this page
IP:[65.110.21.43]
Your face IP:[54.166.39.179]
You are visitor number