I don't think this is true. The loop that sums the values always fetches the array items linearly. Whether they are sorted or not does not make any difference. Since the accumulator ('sum') can be kept in a register there should be no store operations in the inner loop, which means it reduces to simply reading consecutive memory, inspecting the values, and adding some of them to a register.
Branch mispredictions are the only likely cause for the runtime difference. It would be interesting to see whether using multiplexing (sum += data[c] > 128 ? data[c] : 0) or conditional assignments would make any difference. Some CPU's have opcodes for these that don't require branching, but I'm not sure whether they use the branch prediction logic.
Comments
I don't think this is true. The loop that sums the values always fetches the array items linearly. Whether they are sorted or not does not make any difference. Since the accumulator ('sum') can be kept in a register there should be no store operations in the inner loop, which means it reduces to simply reading consecutive memory, inspecting the values, and adding some of them to a register.
Branch mispredictions are the only likely cause for the runtime difference. It would be interesting to see whether using multiplexing (sum += data[c] > 128 ? data[c] : 0) or conditional assignments would make any difference. Some CPU's have opcodes for these that don't require branching, but I'm not sure whether they use the branch prediction logic.