Re: sorting code Steven Deller <[log in to unmask]> Mon, 18 Dec 2000 16:58:39 -0500 text/plain (49 lines) ```Jesse, 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 = 1024 sorting "operations", versus 4096 sorting "operations" doing the whole list. Using an O(N**2) algorithm, sort each one individually, you get 16*256 = 4096 sorting "operations", versus 65536 sorting "operations" doing the whole list. Regards, Steve P.S. The indirectsort approach has one additional benefit, namely you can create a "stable" sort from non-stable sort with just a minor change to the Rearrange_List code. You keep the Li list intact, keep the "sorted" information in an associated bit-array, and then make a final pass to find and rearrange *equal* members to their original order. Let me know if you want the details. ```