Counting Sort

4 9 8 5 5 <== Each one of these elements has a bunch of data associated it, and we want the sort to be stable.

0 1 2 3 4 5 6 7 8 9
0 0 0 0 1 2 0 0 1 1

0 0 0 0 0 1 3 3 3 4




4 5 5 8 9 <== Sorted Array

If you have n elements in your array with k distinct values then you need an extra array of size k, an output array of size n, and the algorithm runs in THETA (n+k) time = THETA (max(n,k)) time.


RADIX SORT:  sorting a deck of cards.  The radix sort is when you want to sort on multiple fields, like, say, ranks and suits.  Or, in real data, zip codes and phone numbers.  Or something with relatively small finite number of values.

In cards:  You want it sorted by suit, and then by rank within each suit.  With the radix sort, you use the counting sort to sort on the least important thing.  So, you would use the counting sort to sort by rank.  Then, you would have all the aces together, all the 2's together, all the 3's together, and so on.  1970's.  And I put the apostrophe before the s, and I put two spaces after the period.

"Eats, Shoots, And Leaves".  "The panda eats shoots and leaves."

"Let's eat, Grandma."

After sorting by the last most important sort field, then sort by the next least important.  In this case suit.

Clubs, Diamonds, Hearts, Spades, but since you had already sorted by rank ,and counting sort is stable, you now have each suit already/automatically sorted by rank within it.

Keep doing this until you get to the most important sort field.

Theta (cn), where c is # number of sort fields and n is the size of the array, assuming that k, the number of possible values is still smaller than n.

BIN SORT / BUCKET SORT.  I have used this sort in real life.

This is where you're floating point numbers or something like and you may have a very large number of possible numbers.  The thing that makes the bucket sort is that you know in advance that they will be uniformly distributed.

You can find the range easily:  what's the largest number in the array, what's the smallest.

Then you take the range and divide it up into n equal pieces where n is the size of the array.

Then I go through each element in the array, work out what "bin" it belongs (using simple math), and now I have n bins, each with about one element in them.  They are essentially sorted now.  However, some bins may have more than one element, and you can sort them using even something stupid like bubble sort.  And now the range is sorted.