Quote: "What's the alternative to a comparison sort?"
There are other sorting algorithms which don't depend on comparisons to function, for example radix sort operates in O(n) time.
A simple example is if you have numbers between 1 and 5 that you want to sort:
5
1
3
4
3
First you count how many of each number there are:
1: 1
2: 0
3: 2
4: 1
5: 1
Then you sum those values to find how many items are less than each number:
< 1: 0
< 2: 1
< 3: 1
< 4: 3
< 5: 4
This tells you exactly where to put each item. The first item is a 5, so you look in the array and see that there are 4 numbers less than 5, so 5 must go in the 5th position. At the same time you increase the value in the counting array. Repeating this process:
Next input: 5
Count: {0, 1, 1, 3, 4}
Result: {x, x, x, x, 5}
New count: {0, 1, 1, 3, 5}
Next input: 1
Count: {0, 1, 1, 3, 5}
Result: {1, x, x, x, 5}
New count: {1, 1, 1, 3, 5}
Next input: 3
Count: {1, 1, 1, 3, 5}
Result: {1, x, 3, x, 5}
New count: {1, 1, 2, 3, 5}
Next input: 4
Count: {1, 1, 2, 3, 5}
Result: {1, x, 3, 4, 5}
New count: {1, 1, 2, 4, 5}
Next input: 3
Count: {1, 1, 2, 3, 5}
Result: {1, 3, 3, 4, 5}
New count: {1, 1, 3, 4, 5}
Obviously you would normally use this on much larger ranges than 1-5. You would normally do this process multiple times, so if you were sorting 4 byte integers, the count array would be far too big, so you might do it one byte at a time, so you'd only have to use an array with 256 items in.
If you want a better explanation, Paul explained it very well at the last TGC convention, the videos of which should still be around somewhere.
[b]
