Re:Timsort
by JoachimSchipper on Wednesday November 09, 2011 @05:05AM
(#3214962)
Timsort isn't intended for uniformly distributed data. In fact, I'm really surprised that quicksort didn't beat introsort in your tests - it may have some nasty edge cases, but you'll never hit those on truly random input and avoiding the (minimal) extra work of introsort should help.
[ Parent
| on HN ]
Timsort optimizes for partially sorted data, but that's a long way from saying it's not intended for uniformly distributed data. It's intended for all data, that's why it's the default sort in Python. It's no less intended for all data than merge sort is.
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.
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
Did you read my post? What I said was nowhere near "it goes quadratic 50% of the time". You're arguing against a straw man.