This example isn't about branch prediction (not exactly), but it might still be interesting:

https://github.com/frankmcsherry/blog/blob/master/posts/2015...

It's about how sorting + random access can be faster than random access, because you introduce locality of reference. And in this case, it absolutely is faster to sort the data first and then do the work, even counting the sorting.

Edit: Aw crap, adrianN beat me to this a few screenfuls down, sorry! But, it is a different post, so maybe this is still helpful. :D