Why is it faster to process a sorted array than an unsorted array?

Question

Why does a sorted array get processed faster than an unsorted array, even though the size of the arrays are same?

According to me, the compiler will have to check each and every value in both the Arrays, so the time taken should be the same. But the sorted array gets processed faster. Why?

Answer 1

It is faster to process a sorted array than an unsorted array because of Branch Prediction.

Now, branch prediction means determining whether a conditional branch in a program is gonna run or not. As the array is sorted, Predicting the Reaction of elements for a particular conditional Statement becomes Easy.

For example -

Consider you have a list of number which are sorted, you pick the first number and it is 3, the next is 5 and so on... , after the second number you can easily predict that all the next number will be greater than 5. Whereas, such a Prediction is not possible in an Unsorted Array.