News for hackers. Stuff that matters.
Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by MaxBarraclough on Saturday May 30, 2020 @05:54PM (#23365103)
I 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.
Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by CJefferson on Sunday May 31, 2020 @04:26AM (#23368104)
You are right. For people who like quicksort, the "timsort of quicksorts" is pattern-defeating quicksort (pdqsort), which is my usual goto algorithm nowadays.
Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by MaxBarraclough on Sunday May 31, 2020 @05:59PM (#23373165)
So does this work out as a three-part hybrid algorithm? Timsort, 'then' Quicksort, then bubble sort/insertion sort for short sequences?
Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by saagarjha on Saturday May 30, 2020 @06:53PM (#23365553)
Since the larger case was using QuickSort, it seems.
Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by MaxBarraclough on Saturday May 30, 2020 @07:22PM (#23365731)
I don't follow. Why put all this work into optimising Quicksort without even mentioning that a superior algorithm has since been discovered?
Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by saagarjha on Saturday May 30, 2020 @07:31PM (#23365790)
I'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.
Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by kzrdude on Sunday May 31, 2020 @05:17AM (#23368290)
Timsort is great in Python and Java; the objects sorted are pointer-sized (cheap swaps) and there is always indirection (expensive comparisons).