Can you sort in less than Theta (n lg n) time?  [ o (n lg n)]

NOT if your only method of distinguishing relative positions is in the form of comparisons.  Comparison-based sorting is intrinsically n lg n.  [There are n! to order a list.  A comparison can only eliminate about of them.  So, the number of comparisons has to be in the vicinity of lg (n!) which is about n lg n.  Because comparison-based is the most generic form of sorting.  It works on any data as long as there is a mechanism for comparing the data, and so this is why we study this.  QuickSort, MergeSort, HeapSort, ShellSort, all of these sorts use comparisons and only comparisons as a way to derive the proper ordering of the data.

However, there ARE sorting techniques that are faster than n lg n.  They only work because the sorts are not generic.  They make assumptions about the data.  If the assumptions are false, the sort might not be so hot.


Suppose I have an array of integers all of which fall into the range [l...h].  I have an array of size h-l+1 which I initialize to zero.  (Call it C).

Then I go through the array one at time and increment the appropriate element in C.  For example, if I see a 5, I increment C[5].

When I'm done, sorting is easy.  How many C[l]'s do I have?  I just load them up into the original array.  How man C[l+1]'s I have?  Just load those up, too, and so forth.

If all of my numbers are in the range [0..9]:

Sort (4 6 2 2 2).

0 0 3 0 1 0 1 0 0 0
_ _ _ _ _ _ _ _ _ _

0 1 2 3 4 5 6 7 8 9

2 2 2 4 6

If n is size of the original array and m is the size of the range.  Then, the algorithm runs in Theta (n+m) time.

So, how am I cheating?  What could go wrong that could slow this down (extremely)?

Generally speaking, you want n >> m.

Alphanumeric strings of length 10 or less.  There are 36 alphanumeric strings, so that 36^0 + 36^1 + 36^2 + ... + 36^10

36(36^10-1)/35     a(r^n-1)/(r-1)

3,760,620,109,779,060


Let's say you're sorting records.  You're sorting on one specific field of the record (student grade level, say) but the records have other stuff (like student name, say), and you still want to preserve that stuff.

One of easiest ways is to store a linked list along with the counts.

So, if you see a kid in fourth grade, increment the fourth grade counter and then add the record to the linked list.  [You don't even need the counter since you have the linked list.]

Then, you're done counting, you can go through the array of linked lists and restore all the records in their proper order.