[cperciva]

Times change. The relative cost of a compare is considerably higher now than it was in 1978, thanks to the cost of branch (mis)predictions.

It's entirely possible that a modification which was a significant loss in 1978 is a significant gain in 2008.

[kragen]

Yes, but the number of comparisons and the number of swaps wouldn't change. Sedgewick and Yaroslavskiy can't both be right, unless anatoly misread something.

[cperciva]

Oops, I misread what he wrote.