To be fair, that is because it is a carefully tuned combination of 3 sort routines (quicksort, heapsort, insertion sort), and also optimisations to avoid unnecessary checks for pointers reaching the end of arrays where they can be avoided.
I would be impressed if a sort which used the same 3 combined techniques could be faster.
(Of course, there might be better sorts, such as TimSort, but that's a change of algorithm, not language).
I think timsort is trying to optimize on comparison counts, because comparisons might call back into Python code, which is expensive. Other sorting algorithms optimize different operations.
Comments
Not to mention that Haskell's sort function is actually quite a bit more complex than the stereotypical "quicksort" example shown.
For reference, Data.List.sort in GHC: http://www.haskell.org/ghc/docs/7.0.2/html/libraries/base-4....
It's still short and sweet ;).
C++'s std::sort in turn is a lot more complex than the quicksort example shown.
To be fair, that is because it is a carefully tuned combination of 3 sort routines (quicksort, heapsort, insertion sort), and also optimisations to avoid unnecessary checks for pointers reaching the end of arrays where they can be avoided.
I would be impressed if a sort which used the same 3 combined techniques could be faster.
(Of course, there might be better sorts, such as TimSort, but that's a change of algorithm, not language).
I think timsort is trying to optimize on comparison counts, because comparisons might call back into Python code, which is expensive. Other sorting algorithms optimize different operations.