3 ms·

How is this different from "Brent's variation of Knuth's Algorithm D"? * https://books.google.com/books?id=e3wLBAAAQBAJ&pg=PA532#v=onepage&q&f=false https://bo

How is this different from "Brent's variation of Knuth's Algorithm D"? * https://books.google.com/books?id=e3wLBAAAQBAJ&pg=PA532#v=onepage&q&f=false https://books.google.com/books?id=e3wLBAAAQBAJ&pg=PA532#v=on... * http://maths-people.anu.edu.au/~brent/pd/rpb013.pdf http://maths-people.anu.edu.au/~brent/pd/rpb013.pdf

jaswilder 10y ago
The author's thesis has some comparisons to Brent's method. See P51-53 https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf for conclusions.
kmill 10y ago
If I remember correctly, Brent's variation considers both the chain of the element being inserted, and the chains for the elements being swapped, and then does a dynamic program to decide exactly what to swap. It sacrifices some insertion efficiency for fewer expected probes for lookups.