2008/3/4, Krzysztof Skrzętnicki
Thanks for improved code. My point was to measure which programming patterns are faster than the others so I can learn which ones I should use. However, the thing that is really bad is the fact, that even oneliner qsort_i is faster than library sort. Which is very different from what I've expected. My intuition is only best and fastest code goes to library, to the point that people can learn from it. It seems I was mislead.
I think you did not correctly got the point of my and Neil Mitchell's message : you benchmarked those function on a completely random sequences so qsort was at his best, but in the real world, most sequences would have bias, and it is not infrequent at all to sort a partially sorted (or reverse sorted) list... In this case the performance of all your qsort are abysmal... Which is the reason the old sort was replaced by the actual mergesort in the library. Try my code (with 10000 elements for example), you'll see that sort is the best on a sorted list, and that qsort is at least 60 times slower (on 10000, in fact it is degenerating in O(n^2)). In the real world, the library maintainers decided it was ok to pay a slight overhead in the case where the list to sort is really randomly distributed since mergesort won so hugely over qsort in the pretty frequent case (in programs) of lists which present regularities. There is no sort which is ideal in all situations, but we can try to get a sort that works well in all situations, and don't trash in situations not so infrequent. (On the other hand, don't expect libraries functions to always be the best to use in your particular situation, they tend to be all-purpose as we just saw and the maintainers prefer simple generic implementations rather than complicated ones who could be slightly (or even significantly) faster in some case) -- Jedaï