Sorting techniques that are faster than Th (n lg n).

Let's say we have an array of records but we are only sorting an a relatively small field within the record.  Like, in a school system, we might sort on grades, understanding that the list is ALREADY in alphabetical order.

Say we have a whole bunch of records.

Abner Grade:7  Bill Grade:2  Charlie Grade:3 David Grade:2  Eilonwy Grade:7 Frances Grade:3  Gina Grade:7  Hortense Grade:2  Ian Grade:2 Janet Grade:3

0 4 3 0 0 0 3 0 0  0  0  0  <== This array counts the distinct items to be sorted

1 2 3 4 5 6 7 8 9 10 11 12

0 0 4 7 7 7 7 10 10 10 10 10  <== This is a running total of the count array

Now rebuild our array backwards.

1: Bill Grade:2
2: David Grade:2
3: Hortense Grade:2
4: Ian Grade:2
5: Charlie Grade:3
6: Frances Grade:3
7: Janet Grade:3
8: Abner Grade:7
9:  Eilonwy Grade:7
10: Gina Grade:7


Radix Sort:

You have a bunch of file cards (or 3x5 cards) and you want them in alphabetical order.  Each card has a certain fixed number of holes at the top (all with the same number of holes and with the holes aligned).  Some of the holes are actually slots; the hole extends to the top of the card, but others are just holes.  Each card is unique with respect to its pattern of holes and slots.

Now:  what the pattern actually is a binary number of some kind with the holes representing zeroes and the slots representing ones.  And the binary number is some sort of encoding of the name on the card that preserves the alphabetical order:  names that come earlier in alphabetical order have a lower binary number and this number is represented with holes and slots.

You can sort the cards with a ball point pen...or a long metal rod if you have too many cards for a ball point pen.

Align the cards, stick the pen through the right-most hole in the cards and lift up.  The ones with holes are still on the pen.  The ones with slots fall off the pen.  Then take the ones with holes and move them in front of the ones with slots.

Do the same thing for the hole second-to-the-right, and so forth, and so on, ending with the left-most hole.  And now your cards are in alphabetical order.

1 1 0 1
1 0 0 1
0 1 1 0
1 0 1 1
0 0 0 0

0 1 1 0
0 0 0 0
1 1 0 1
1 0 0 1
1 0 1 1

0 0 0 0
1 1 0 1
1 0 0 1
0 1 1 0
1 0 1 1

0 0 0 0
1 0 0 1
1 0 1 1
1 1 0 1
0 1 1 0

0 0 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1

The radix sort is used when you want to sort on several different fields.  Usually, these are fields with a small number of possible values (like student grades, not like student names).

You sort on the LEAST important item first, using counting sort.
Then on the SECOND LEAST important item.
And so forth, finally on the MOST important item.

So, if I want to sort by grade, and within grade, sort by birthday.  I would sort on birthday first because that is least important.
And then I would sort by grade.

The reason this works is that counting sort is stable.

Stable:  Items that are equal on the sort field will be in the sorted array in the same relative order that they were in in the original array.

You know that they are in order by grade because that is the last thing you sorted by grade.  They are no longer totally sorted by birthday (because you subsequently sorted them by grade) but because counting sort is stable if two items have the same grade they will appear in the same relative order in the final array AND since they had been ordered by birthday that order will be preserved within the grade in the final array.