3 ms·
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
by JoachimSchipper 15y ago
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.
- shin_lao 15y agoIntrosort only adds a depth check and size check to each recursion, that's only a couple of instructions with little memory access.
- jemfinch 15y agoTimsort 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.
- JoachimSchipper 15y agoDid 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 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
- jemfinch 15y agoDid you read my post? What I said was nowhere near "it goes quadratic 50% of the time". You're arguing against a straw man.