+7 votes
2 views
in Java by (1.4k points)
recategorized by

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?

1 Answer

+13 votes
by (13.2k points)

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.

Related questions

0 votes
1 answer
0 votes
1 answer
asked Aug 1 in Python by ashely (42.1k points)
0 votes
1 answer
asked Jul 13, 2019 in SQL by Tech4ever (20.3k points)
Welcome to Intellipaat Community. Get your technical queries answered by top developers !


Categories

...