4 ms·

Timsort doesn't have n^2 worst case performance. Also, CPython's sort is implemented in C, no need for copying: http://hg.python.org/cpython/file/be77b213ace0/O

• bluecalm 12y ago
  It is implemented in C but it doesn't sort small structs without any pointer dereference. That quicksort have n^2 worst case scenario doesn't matter in practice at all. First you can make it nlogn (by either running heapsort at some point or taking median out of 3-5 random elements instead of once at predermined positions).