That's for sure!...
Branch Prediction makes the logic run slower, because of the switching which happens in the code! It's like you are going a straight street or a street with a lot of turnings, for sure the straight one gonna be done quicker!
If the array is sorted, your condition is false at the first step: data[c] >= 128, then becomes a true value for the whole way to the end of the street. That's how you get to the end of the logic faster. on the other hand, using unsorted array, you need alot of turning and processing which make your code run slower for sure...
Look at the image I created for you below, which street gonna be finished faster?
So programmatically, Branch Prediction causes the process be slower...
Also at the end, it's good to know we have 2 kinds of branch predictions that each gonna effects your code differently:
1. static
2. dynamic
Static branch prediction is used by the microprocessor the first time a conditional branch is encountered, and dynamic branch prediction is used for succeeding executions of the conditional branch code.
In order to effectively write your code to take advantage of these rules, when writing if-else or switch statements, check the most common cases first and work progressively down to the least common. Loops do not necessarily require any special ordering of code for static branch prediction, as only the condition of the loop iterator is normally used.