In computer architectures, branch prediction "works" only to the extent that the probability of one arm is substantially smaller than the other arm. If both arms are equally likely, then many/(most?) branch prediction schemes will actually do worse, since the overheads for the branch prediction scheme aren't paid for on either arm. The best sorting algorithms arrange for the comparisons to be "most informative" -- i.e., their branch probabilities are very close to 1/2 -- so traditional "branch prediction" isn't going to be very helpful. Now to the extent that you can defer branches and deal with the consequences later may allow you to overlap some activity so that previously sequential operations are now in parallel. However, you should be aware that for most modern CPU's, things like "instruction fetch" are more-or-less free, since instruction fetch units typically fetch instructions from both branch paths. At 04:58 PM 5/20/2014, Warren D Smith wrote:
Suppose you are doing quicksort. Zoing, zoing, zoing, you do compares, and suddenly you decide "aha! this last comparison tells me I need to swap item[K]!" And then you branch off someplace else in your program to do it. Big lose. Mispredicted branch.