C++でソート済み配列の処理が未ソート配列より速い理由とは？分岐予測の仕組みを解説

はじめに：ソートの有無で処理速度が変わる理由

C++において、ソート済みの配列は未ソートの配列よりも高速に処理できることがあります。その鍵となるのが「分岐予測（Branch Prediction）」というCPUの仕組みです。

コンピュータアーキテクチャにおける分岐予測とは、プログラムの命令フロー内に含まれる条件分岐（ジャンプ）が「実行される可能性が高いか、そうでないか」をCPUが事前に推測する機能のことです。この予測が当たれば、パイプラインが中断されることなく処理が進むため、実行速度が大幅に向上します。

具体例で見る分岐予測の動作

以下のようなコードを例に考えてみましょう。

if(arr[i] > 50) {
    // 操作Bを実行
} else {
    // 操作Aを実行
}

このコードを100個の要素に対して、「未ソート」と「ソート済み」それぞれの状態で実行すると、何が起こるのでしょうか。

ケース1：ソート済み配列の場合

配列が昇順に並んでいる場合、データとそれに対応する操作は次のようになります。

1, 2, 3, 4, 5, …… 50, 51, …… 100
A, A, A, A, A, A, B, B

この場合、最初の50個はすべて操作A、残りの50個はすべて操作Bというように、分岐のパターンが規則的です。CPUは正しい分岐をパイプラインに正しい順序でロードできるため、予測はほぼ外れません。

A, A, A, A, A, A, A, B, B

ケース2：未ソート配列の場合

一方、配列がバラバラの順序で並んでいる場合はどうでしょうか。

5, 51, 6, 90, 4, 49, 60……
A, B, A, B, A, A, A, B

この場合、操作Aと操作Bが不規則に入り混じるため、分岐予測はほとんど機能しません。AとBのどちらが実行されるかを正確に予測することは非常に困難で、予測ミス（分岐ミスペディクション）が頻発します。

まとめ

予測ミスが発生するたびに、CPUはパイプラインをフラッシュして再実行する必要があり、これが大きな性能低下につながります。つまり、データを事前にソートしておくことで分岐予測の命中率が上がり、全体的な処理速度が向上するのです。これはアルゴリズム計算量（O記法）では表れない、ハードウェアレベルでの最適化効果の一例といえます。