マージソート

マージソートは配列を二つに分け、それぞれを整列してから結合します。分割を繰り返すと一要素の区間になり、各区間は整列済みとみなせます。結合では、二つの整列済み列の先頭を比べ、小さい方から出力します。

入力の順序によらず時間計算量は O(n log n) です。このレッスンでは O(n) の補助配列を使います。同値なら左側を先に出力するため、元の順序を保つ安定ソートです。

マージソートの仕組み

sort(lo, hi) は中点 mid で区間を分け、[lo..mid] と [mid+1..hi] を再帰処理します。一要素以下なら終了します。両側の整列が終わったら、二つを結合します。

結合中、i は左側、j は右側の未出力要素の先頭を指し、k は補助配列の書き込み位置を指します。arr[i] <= arr[j] なら左を出力して i を進め、それ以外なら右を出力して j を進めます。どちらも、出力後に k を進めます。

片側を使い切ったら、もう片側の残りを順に出力します。最後に補助配列の [lo..hi] を元の配列へ戻します。補助配列は一度確保し、各結合で再利用します。

同値で左を選ぶ <= が安定性を支えます。左の区間にある要素は、右の区間の要素より元の位置が前です。結合でこの関係を保てば、全体でも同値の順序が保たれます。

マージソートのステップ

初期入力は [38, 12, 56, 7, 12, 41, 23] です。元の添字 1 の 12 を 12a、添字 4 の 12 を 12b とします。

分割。 [0..6] の中点は 3 です。左側 [38, 12a, 56, 7] と右側 [12b, 41, 23] に分け、一要素になるまで再帰します。

左側の結合。 [38] と [12a] から [12a, 38]、[56] と [7] から [7, 56] を作ります。二つの先頭を比べ、7、12a、38 の順に出力します。左側を使い切ったので 56 を追加し、[7, 12a, 38, 56] を得ます。

右側の結合。 [12b] と [41] は [12b, 41] になります。これを [23] と結合し、[12b, 23, 41] を得ます。

最後の結合。 まず 7 を出力します。次に 12a と 12b が並ぶと、<= により左の 12a を選びます。その後は 12b、23、38、41 を出力し、残る 56 を追加します。結果は [7, 12a, 12b, 23, 38, 41, 56] です。二つの 12 は元の順序を保っています。

アニメーションでは分割する区間、左右の読み取り位置、補助配列への書き込みを対応させて見ます。結合の途中では、元の配列と補助配列が別の状態を持ちます。元の配列へのコピーで、その区間の結合が完了します。

時間・空間計算量

分割の深さは O(log n) です。各深さで結合する要素数の合計は O(n) なので、全体で O(n log n) になります。入力が昇順でも、この実装は結合を省略しません。

補助配列は O(n)、再帰スタックは O(log n) です。合計は O(n) で、この実装は追加領域 O(1) のインプレースソートではありません。入力順序による二乗時間への退化がなく、安定性も保てます。

境界条件

• 空区間・一要素：結合せず終了します。
• 整列済み：正しい順序を保ちますが、分割と結合は行います。
• 逆順：左右の値の選ばれ方は変わりますが、計算量は O(n log n) のままです。
• 重複値：同値で左を選ぶため、元の順序が保たれます。
• 要素数が奇数：区間の長さが一つ違っても処理できます。初期入力では左が四要素、右が三要素です。

よくある間違い

• 比較を < にする：同値で右を選び、安定性を失います。
• 片側の残りをコピーしない：主ループは片側が尽きた時点で終わるため、要素が欠けます。
• 補助配列全体を戻す：対象外の位置には以前の結合の値が残ることがあります。[lo..hi] だけを戻します。
• 結合のたびに補助配列を確保する：一つの配列を再利用すれば、確保の回数を減らせます。
• 再帰呼び出しだけで終える：左右がそれぞれ整列しても、区間全体はまだ整列していません。結合が必要です。