2 ms·
I don't follow. Why put all this work into optimising Quicksort without even mentioning that a superior algorithm has since been discovered?
by MaxBarraclough 6y ago
I 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).