Insertion sort gets penalized if comparison or copying is slow. In other words, the maximum array size which is faster to sort with insertion sort compared to O(nlogn) algorithms gets smaller if comparison or copying of the array elements is slow.
Shell sort is a very viable alternative to heap sort (at least with arrays of up to 1 million elements). If comparison or copying of the elements is slow, shell sort might even be slightly faster.
Shell sort seems especially suited to the case where there's a
sorted array with a small unsorted section of elements at its end,
beating even (the linux gcc) std::sort in most cases.
With other element distributions it is slower (sometimes significantly).
Shell sort also seems to benefit from repetition in the array.
No surprises. Basic trustworthy O(nlogn). Seems to
be slowest with very large arrays with completely random elements.
Significantly slower than std::sort.
Surprisingly fast, at least with the optimizations used in this test (ie. the sorting function doesn't need to allocate the secondary array each time it is called). Given that it is always O(nlogn), it is a very good alternative if the extra memory requirement is not a problem.
Array elements with fast comparisons and slow copying seem to slightly penalize merge sort.
Showed clearly its unpredictable nature, even when optimized. When it worked well, it was very fast, but with pathological cases it was really slow.
The reason why the "random end" test was pathological for the optimized quicksort is a complete mystery. One has to simply conclude that optimizing quicksort is far from trivial.
Vanilla quicksort seems to get penalized if comparison is slow (but copying fast). If comparison is fast it suffers no penalty even if copying is slow.
As expected, a sure bet. This standard function has been developed for many years and a lot of algorithmical expertise has been poured into it, and thus it performs in average very well and has no pathological cases (or they are rather hard to find). It can be beaten in individual cases, but in the general case, ie. in average, it's very difficult.
(The speed of std::sort seems to depend on the platform
too. I have performed similar tests on a Sparc/Solaris computer and I
was completely unable to beat this function there. In linux
it is possible in some individual cases for some reason.)
It's still hard to answer this question with certainty, as I tested
only a few cases. However, in the average case it seems that, not
surprisingly, std::sort gives the overall best times,
even though in individual cases some other algorithms may be a bit
faster.
std::sort uses a highly optimized quicksort enhanced with
insertion sort and heap sort, and possibly some other tricks.
Merge sort got close and even beat it in a few cases. In average it was slower, though.