4 ms·
My intuition about sorting in Python is that by far the fastest way would be to calculate keys first then call an optimized C quicksort on arrays of structs {ha
by bluecalm 12y ago
My intuition about sorting in Python is that by far the fastest way would be to calculate keys first then call an optimized C quicksort on arrays of structs {handle, key} and copy it back to Python. That would require more than 2n memory (and exactly 2n for things like ints or chars) but the speed-up should be huge because well implemented C quicksort on small structs really shines when it comes to exploiting characteristics of modern hardware (cache hits are more important than number of comparisons).
- zeckalpha 12y agoTimsort 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/Objects/listobject.c#l2037 http://hg.python.org/cpython/file/be77b213ace0/Objects/listo...
- bluecalm 12y agoIt 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).