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
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.