Re:Timsort
by JoachimSchipper on Wednesday November 09, 2011 @11:53AM
(#3216236)
Did you ever actually time qsort? It's variability is nowhere near "it goes quadratic 50% of the time". Timings from http://www.joachimschipper.nl/posts/20111109/qsort_timing.c (portable C, note the appended non-introspective qsort() implementation):
qsort: 39 mergesort: 39 qsort: 38 mergesort: 40 qsort: 37 mergesort: 39 qsort: 38 mergesort: 40 qsort: 38 mergesort: 40 qsort: 38 mergesort: 40 qsort: 38 mergesort: 39
Even on random data, 50% of the time you'll pick a bad pivot. Get a slightly unlucky run and you're into quadratic behavior for that subset; the more data you're sorting, the more likely introsort's switch to heapsort on deep recursion (and insertion sort on small ranges) will help.