P Witte wrote: > Quicksort is so much faster than any stable sort I know > of, even when "cheating", that its worth it ;o) > Yeah, yeah. I, of course, agree totally. I cheat /all/ the time.
I did get a bit carried away... and perused the current net thinking on sort algorithms, and it would seem that the ancient "mergesort" has a lot going for it. You add O(n) extra memory to extend the key and make "quicksort" effectively stable. This adds cost to key comparisons. With "mergesort", a similar O(n) extra memory /may/ be needed. However, and this is a /big/ however, the worst case (admittedly low probability) time for "quicksort" is O(n*n), whereas "mergesort" stays at O(n*ln(n))... indeed, its worst case is only twice as slow as its best case. I said above that extra memory /may/ be needed, because it depends on how the data is held. There is /no/ extra memory (barring O(ln(n))) if the data starts off as a linked list. The algorithm is also highly effective if the data is stored on disc, etc, rather than in memory. Algorithm for "mergesort": If more than one element, split (arbitrarily) into two equal (or differ by one) chunks, recursively mergesort each, merge the two sorted chunks. 3767376 split 376 7376 split 3 76 7376 split 3 7 6 7376 merge 3 67 7376 merge 367 7376 split 367 73 76 split 367 7 3 76 merge 367 37 76 split 367 37 7 6 merge 367 37 67 merge 367 3677 merge 3366777 And now... my fertile mind... what if the "split into two chunks" actually was the odd and even indices within the array? Curiously, this could be done as a SuperBasic slice. The merge operation becomes /horrible/, and I haven't thought it through at all (except that the worst case looks to be O(n*n)!), but the whole thing becomes (close to) in-place. PS. I always feel "shellsort" is magic. PPS. <http://en.wikipedia.org/wiki/Patience_sorting> looks rather interesting. _______________________________________________ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
