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

Question

I ran some tests and found out that, for some reason, the sorted array is faster to process. I believe there is something about assembly here (low-level stuff).

Answer 1

I found out that the reason for this is the event called branch prediction. In Layman's terms it means that if a train knows the order of the junction (sorted) then it will not have to return and go to the oposite direction. If the conductor doesn't know where to go, if he chooses the wrong side he will have to return back and go to the right side.

Answer 2

I don't see why it should be faster...
What exactly is faster though? Creating the array? Accessing the elements?

Answer 3

Accessing and doing arithmetic operations on the elements.

Answer 4

you can count 1 to 10 within in a sec, but when it will count in in order list , it will take more sec than the ordering list

Answer 5

What do you mean by 'process'?
Both ordered and unordered array access is the same O(1). (since you exactly know where the array starts in memory and which element you need)

Searching is of course faster with ordering. You need to travel the generic array from start to finish to search which is naturally O(n).
Ordered one on the other hand has binary search which is O(log n) - which is better in the long run.

We are not concerned about insertion/deletion in static array case.

Answer 6

Accessing elements should always be the same, since the computer stores the start address of the array (the pointer itself) and only adds
N * sizeof(type)
to the start of the array where N is the number of the elements you wish to access. This is why you can access out of bonds as well (11th element in a 10 size array etc).

So after all, sorting only matters in algorithms such as searching.