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. But instead: When your comparison sees a bad item, you conditional-load that item's ID number into a stash (no branching needed) and continue on. Eventually your stash gets full and you have to do a real branch to deal with that, but with a large enough stash-size, this can be made arbitrarily rare. When the stash fills up (or reach end), we do all the swaps of stashed bad items (emptying the stash), then branch back to main code. This stashing technique of "deferring" all the branches, then you later do all the stuff those branches were going to do -- but almost without any branching -- presumably is of pretty general applicability as a high performance programming technique. Certainly it is applicable to quicksort. I don't know what other problems it is applicable to, but probably many. This should yield substantial speedups for the right problems. (Any suggestions?) Meanwhile, in preliminary work, I invented a different new way to substantially speed up quicksort, which finally beat my heapsort implementation (which in turn beat both the currently most-ballyhooed quicksort codes, by Bentley+McIlroy, and by Kushagra et al, in my speed tests). Some version of this stashing idea now might increase that lead, but haven't tried it yet. Anyhow, at least in principle, quicksort now has excellent caching behavior, excellent branch misprediction rates, and arbitrarily near-optimal comparison counts (with good pivot choices) all in one algorithm. Suckily large move counts, though. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)