參考/部分翻譯：https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array
Why is processing a sorted array faster than processing an unsorted array?
在撰寫程式時，評估時間複雜度是一個非常重要的步驟，以確保程式運行的足夠快，滿足需求。
舉例而言，排序陣列是一個耗時的操作，減少使用通常能大幅降低程式的執行時間。但是，在 Stack Overflow 上，卻出現了一個奇妙的問題：「為什麼程式碼中多寫了一行排序，會使得整個程式變快呢？」
#include <algorithm>
#include <ctime>
#include <iostream>
int main()
{
// 建立大小 32768 的亂數陣列
const unsigned arraySize = 32768;
int data[arraySize];
for (unsigned c = 0; c < arraySize; ++c)
data[c] = std::rand() % 256;
// 多加了一行排序，下方程式會變快約 3 倍
// aka 移除這行，下方程式會大幅度變慢
std::sort(data, data + arraySize);
clock_t start = clock();
long long sum = 0;
// 為凸顯效果，重複主迴圈 100000 次
for (unsigned i = 0; i < 100000; ++i)
{
// 主迴圈：遍歷亂數陣列，計算大於 128 的值的和
for (unsigned c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
}
}
double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << std::endl;
std::cout << "sum = " << sum << std::endl;
}
上述的程式目的是：找出陣列內大於 128 的數字，並將其加總。 整個程式分成三部分：
std::sort 來排序這個陣列其中，第二步驟的「排序」與程式邏輯並無關聯，我們嘗試看看移除與否對性能造成的影響。
顯而易見的，「有事先排序」的版本比「無事先排序」的版本快。這主要是受到了 分支預測（branch prediction）的影響。
想像一個情況，在通訊不發達的 1800 年代，你站在改變列車軌道的操縱杆旁，你並不知道下一輛列車想往左還往右，因此你只能每次都請列車長減速，並告訴你他的目的地，然後你再以此判斷。
顯然這是一個很沒有效率的做法，因為不論列車目的為何，都需要減速與你溝通。
有一個更好的想法是，我們來猜下一輛列車的目的地！
所以如果你總是都能猜對，列車將不需要停下，節省了大量時間。如果你時常猜錯，那麼就會耽擱許久。而這就是分支預測的基本概念！
現代 CPU 就和你一樣，手握著操縱杆。當程式有 if 語句時，就會被迫面臨二選一的運氣大挑戰。如下圖，cmp 指令代表先比較誰大誰小，jle 代表左邊 ≤ 127 則跳過 25 行。
這大體上就是分支預測的概念，雖然火車並不是很好的類比，實際上 CPU 是因為 pipeline 的緣故才需要去猜測分支方向。