Value of microeffiency (was: Re: Optimal ...)

[Richard A. O'Keefe]

In article <12369 at mimsy.UUCP> chris at mimsy.UUCP (Chris Torek) writes:
>This is true, but be careful: theoretical average performance on
>theoretical average data is not the same as actual performance on
>actual data.  For instance: [bsort -vs- qsort]
>In the `usual' case, qsort wins by great leaps.  But what if the
>array is already sorted?
>In practise, I have used a routine which either does an insertion
>sort or a quicksort, depending on how scrambled the data are
>expected to be.  Profiling showed that this worked quite well.

There is no substitute for checking the literature.  According to all
three of Knuth V3, Melhorn, and Sedgewick, the average case of quick-
sort does about 1.4 times as many comparisons as the *worst* case of
merge-sort.  Merge sort is stable,  which means that sorting with a
sequence of keys is easy.  What is more, the natural merge exploits
existing order with the utmost ease.