Mon, 18 Dec 2000 16:58:39 -0500
One last thing I missed in your original questions:
> One of the thing I wonder about, is should I have my program
> sort the whole array in one step, or have my code step thru each Letter
> Prefix. If I have it go thru and just do a Letter worth at a
> time, it will
> almost certainly always be under 20 things to sort per letter. Because of
> the small number of objects I would be sorting in this case, I'm also
> considering shell sort, or insertion sort.
Without a doubt you should sort the array "one letter at a time".
The best algorithms are O(NlnN). Consider the following:
N NlnN N**2
2 2 4
4 8 16
8 24 64
16 64 256
256 4096 65536
512 4608 262144
1024 10240 1048576
So let's say you have 256 total items, with 16 letters of 16 items each.
Using an O(NlnN) algorithm, if you sort each one individually, you get 16*64
sorting "operations", versus 4096 sorting "operations" doing the whole list.
Using an O(N**2) algorithm, sort each one individually, you get 16*256 =
sorting "operations", versus 65536 sorting "operations" doing the whole
P.S. The indirectsort approach has one additional benefit, namely you can
a "stable" sort from non-stable sort with just a minor change to the
code. You keep the Li list intact, keep the "sorted" information in an
bit-array, and then make a final pass to find and rearrange *equal* members
original order. Let me know if you want the details.