should be replaced by

“Inside this loop, if conditional moves were used as proposed in the source, the number of element moves would increase from 2N to 3N, so two of the element moves were left behind conditional branches.”

The main loop is iterated N times and during these iterations about N/2 subtree roots are processed. The element moves out from the roots and back into their final destinations were left behind conditional branches. The promotions involve N element moves. Hence, the number of element moves would be about 3N with conditional moves and about 2N with conditional branches. All three conditional branches inside the main loop were predicted well since the underlying hardware used a dynamic branch predictor. Thanks to Andrei Alexandrescu for popping up the topic "branch misprediction" and forcing us to look at our old code again.

[Authors’ version corrected, 23 May 2020]