**Non-Comparison
Based Sorting Algorithms**

In the previous lessons we discussed three basic sorting
algorithms, bubble sort, insertion sort and selection sort, each of which is
easy to implement, but takes O(n^{2}) steps in
average case to sort a list of size n. More advanced recursive algorithms like
Quick Sort and Merge Sort are hard to implement, but runs more efficiently on a
set of data, typically in O(n log n) steps. All five
algorithms assume comparison of the whole key to make the decision to sort. There
are simpler algorithms that can sort a list using partial information about the
keys. There are two algorithms we discussed in this section called Bucket Sort
and radix Sort.

**Bucket Sort**

The idea
of the bucket sort is to place items into various buckets based on a key or partial information about a key. For example, if we
have a list that contains only numbers from 0.. 99,
then we can take 10 buckets and place all elements that are between 0..9 into first bucket, 10..19 into second bucket etc. This
is a kind of sorting that only requires O(n) steps. A
more general sorting algorithm is the radix sort that works as follows.

**Radix Sort**

Suppose
we are able to compare parts of the data to make a decision. Say we have a bunch
of numbers we need to sort. Assume we have the following numbers.

12, 67,
45, 42, 18, 60

Assume
we have 10 buckets we can work with. First we place each item in the bucket
based on the least significant digit (that is 1 place). So we have the numbers
in buckets as follows.

42

60 12 45 67 18

0 1 2 3 4 5 6 7 8 9

Next we
sort the numbers again by second digit (that is 10 place)
and place them in buckets. In the process we need to make sure that we are not
changing the order of the elements.

18 45 67

12 42 60

0 1 2 3 4 5 6 7 8 9

Now note
that if we just collect the numbers from left to right, and bottom to top in
each bucket, we have a sorted list of numbers. This is called the Radix Sort
and complexity of the Radix Sort is O(nb) where b is the number of digits in the largest number.

Note
radix sort can be applied to data that can be compared partially like integers
of characters. However, Radix sort cannot be applied to data that needs to be
compared as a whole (eg: nodes)