Re:Hoare’s Rebuttal and Bubble Sort’s Comeback
by gerbenst on Saturday May 30, 2020 @09:42PM
(#23366497)
The "hybrid" as used in this article referred to a partition scheme that combines a "Lomuto partitioning like algorithm" together with a "Hoare partitioning like algorithm".
This amplifies the the strength of each scheme and mitigates the weakness. Ie. Lomuto does too many swaps, but naturally fits a branchfree implementation. Hoare is frugal with swaps, but is rather branchy. The "hybrid" here inherits the frugality of swaps from Hoare's scheme, while benefits from the branchfree implementation of Lomuto scheme.
What you seem to describe here is the classical and well-known hybridization of divide and conquer algorithms. This is also used and implicitly implied when branchless bubble sort is discussed. But the "hybrid" as used in the article wasn't meant to refer to this.
Re:Hoare’s Rebuttal and Bubble Sort’s Comeback
by MaxBarraclough on Sunday May 31, 2020 @07:16AM
(#23368779)
Thanks.
As the article says, hybrid algorithms can make good sense, where you use a clever algorithm to break down large problems into many small problems, and use another simpler algorithm to solve the small problems. As the article says, in sorting, it makes sense to use something like quicksort to break down large problems, and to then use bubble sort to solve the resulting small problems. In matrix multiplication, it makes sense to use the mind-bending Strassen algorithm (with superior time complexity compared to the naive algorithm) to break down multiplications of large matrices, and to then use the naive algorithm to solve the resulting small matrix multiplication problems. [0]
The threshold for switching over to the clever solution increases year on year, as hardware improves. Clever algorithms tend to behave worse in terms of branch-prediction and cache.
Apparently a similar thing occurs in large integer multiplication. [1] I'm sure there are plenty of other examples besides.
Related: Of all the known matrix multiplication algorithms, the ones with the best time-complexity are never used in practice, as their constant factors spoil things. [2]
[0] https://en.wikipedia.org/wiki/Strassen_algorithm#Implementat...
[1] https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse...
[2] https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a...