4 ms·
No mention of Timsort though.
by zitterbewegung 6y ago
No mention of Timsort though.
- CJefferson 6y agoFor this case, in tiny arrays, something like timsort would be a bad idea -- the basic idea of the article is that it takes so little work to sort tiny arrays that you want to run the simplest algorithm possible.
- pjscott 6y agoFor tiny arrays, Timsort uses insertion sort.
- MaxBarraclough 6y agoI think the Fallback for sorting short arrays section makes it clear that it's not only about sorting small arrays, so I think it's reasonable to wonder why Timsort wasn't mentioned.
- saagarjha 6y agoSince the larger case was using QuickSort, it seems.
- MaxBarraclough 6y agoI don't follow. Why put all this work into optimising Quicksort without even mentioning that a superior algorithm has since been discovered?
- saagarjha 6y agoI'm not sure how you came to the conclusion that Timsort is "superior". As far as I was aware, Quicksort generally does better on random lists and on primitive datatypes? Timsort is often used for its strengths: it's stable, it does better on partially sorted data, etc. Keeping this in mind, this article specifically focuses on optimizing the "small array" case of Quicksort, because it forms an important part of the performance profile of the algorithm in the places where it is used.
- kzrdude 6y agoTimsort is great in Python and Java; the objects sorted are pointer-sized (cheap swaps) and there is always indirection (expensive comparisons).
- CJefferson 6y agoYou are right. For people who like quicksort, the "timsort of quicksorts" is pattern-defeating quicksort (pdqsort), which is my usual goto algorithm nowadays.
- MaxBarraclough 6y agoSo does this work out as a three-part hybrid algorithm? Timsort, 'then' Quicksort, then bubble sort/insertion sort for short sequences?
- zucker42 6y agoTimsort is not in place, and is essentially similar to mergesort. Most libraries use quicksort for sorting primatives, so it's the right thing to compare to.