Hoare’s Rebuttal and Bubble Sort’s Comeback

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by megameter on Saturday May 30, 2020 @06:36PM (#23365433)

I wonder if they tried shell sort? IME it's so close to bubble sort in implementation that you can view it as a trivial optimization.

[ Parent | on HN ]

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by kzrdude on Saturday May 30, 2020 @08:04PM (#23365984)

And just a few shells could be added, to make this optimization right? If the sequence is 1, 4, 10, 23, .. one could start by just adding a pass with 4 and then 1.

https://stackoverflow.com/questions/2539545/fastest-gap-sequ...

I don't know how to select the fallback sort loop size (related to cache line size maybe?); in his github code he uses 16 elements as the threshold.

[ Parent | on HN ]

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by gerbenst on Saturday May 30, 2020 @10:27PM (#23366660)

A very interesting suggestion indeed. Shell sort is an insertion sort though. It owes its better complexity from being able to breaking out of loop early. But these are difficult to predict branches that bubble sort avoids.

Certainly this is worth an experiment

[ Parent | on HN ]

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by kzrdude on Sunday May 31, 2020 @05:03AM (#23368240)

Well, you are the expert :). I misremebered and thought of the base case for shell sort to be a kind of bubble sort.

[ Parent | on HN ]