Re: Smart sorting algorithm ?

["Ron" <ron@no.spam>]

First, I hope Wes has investigated non-comparison-based sorting...

Second, Wes never indicated the number of items to sort, but used small
values (18 and 36) as examples.  If you only want to sort a small number of
items, then the On-Line Encyclopedia of Integer Sequences
(http://www.research.att.com/~njas/sequences/index.html) may be of help:
To sort 18 items (referenced by sequence number):
A036604 lists the minimal number of comparisons needed to sort n elements,
but only goes up to n=12.
A003070 gives 53 for ceiling(log_2 n!) (the lower bound on number of
comparisons required for comparison-based sorting)
A001768 gives 54 comparisons for merge sort
A001855 gives 59 comparisons for sorting by binary insertion
A003071 gives 67 comparisons for sorting by list merging
A006282 gives 82 comparisons for Batcher's parallel sort (which can be
implemented via a sorting network)
Also, the best sorting network I'm aware of requires 79
comparison-exchanges.

Third, quicksort isn't very good for a small number of items because of its
worst-case performance and overhead, which is why most sorting algorithms
based upon quicksort us another sorting method once the sub-lists are small.

Good luck!


- Ron Zeno