|
Now, the good answer, and essentially what the grandmother gave, is essentially just old radix sort like punch cards were sorted. Radix sort? Take a deck of punch cards with a non-negative integer in base 10 right justified in some three columns. Run the cards through the sorter sorting on the least significant digit. The sorter puts each of the cards into the right one of 10 pockets, one for each of 0-9. Or just imagine that it builds 10 'linked lists'. Then move the cards back to the input, 0 pocket first, then the 1 pocket, etc. Then sort on the 10s digit column. Then repeat on the 100s digit column. Done. Just did the work in time proportional to 3*n for n cards. If have a sorter with 1000 pockets, then can do the sorting in one pass. For the ages, such a sorter would sort all the input in just one pass. Also cute, radix sort is 'stable' which means if card A starts before card B and if these two cards have the same value on the sort key then at the end card A will still be ahead of card B. Stable sorts are nice because they can permit sorting on several keys separately and, then, have the whole list of records in sort on the 'hierarchical key' made from 'concatenating' the separate keys. Again, can do it all playing with pointers and linked lists. It remains, for short keys, radix sort is faster than the (n)ln(n) sorts. |