Radix Sort

Radix Sort is an algorithm that sorts a list of numbers and comes under the category of distribution sort.

Radix Sort is a smart and intuitive little sorting algorithm. Radix Sort puts the elements in order by comparing the digits of the numbers.

This sorting algorithm doesn't compare the numbers but distributes them, it works as follows:

• Sorting takes place by distributing the list of number into a bucket by passing through the individual digits of a given number one-by-one beginning with the least significant part.

• After each pass, the numbers are collected from the buckets, keeping the elements in order.

• Now, recursively redistribute the elements as in the above step '1' but with a following reconsideration: take into account next most significant part of the number, which is then followed by above step '2'.

Consider the following 9 numbers:

493 812 715 710 195 437 582 340 385

We should start sorting by comparing and ordering the one's digits:

Notice that the numbers were added onto the list in the order that they were found, which is why the numbers appear to be unsorted in each of the sublists above. Now, we combine the sublists (in order from the 0 sublist to the 9 sublist) into the main list again:

340 710 812 582 493 715 195 385 437

Now, the sublists are created again, this time based on the ten's digit:

Now the sublists are gathered in order from 0 to 9:

710 812 715 437 340 582 385 493 195

Finally, the sublists are created according to the hundred's digit:

At last, the list is combine up again:

195 340 385 437 493 582 710 715 812

And now we have a fully sorted array! Radix Sort is very simple, and a computer can do it fast. When it is programmed properly, Radix Sort is in fact one of the fastest sorting algorithms for numbers or strings of letters.