マージソート — Project Hematite

これまで見てきたすべてのソート — バブル、選択 — は最悪ケースで $\Theta(n^2)$ かかる。 $n = 10^6$ 要素では約 $10^{12}$ の操作：非実用的だ。マージソートはこの壁を破る。より小さな構造的な問いを解くことで、最良・最悪・平均すべてのケースで $O(n \log n)$ かかる：2 つのソート済み配列をマージするのは安価なのだから、マージすることでソートすればよい。

中心的なアイデア：分割・統治・マージ

マージソートは分割統治（divide and conquer）アルゴリズムだ。3 つのステップで動作する：

分割 — 配列を中点で左半分と右半分に分割する。
統治 — 各半分を再帰的にソートする。
マージ — 2 つのソート済み半分を 1 つのソート済み配列に結合する。

基底ケースは 0 または 1 要素の配列で、定義により既にソートされている。

アルゴリズムの力はステップ 3 にある。合計長 $n$ の 2 つのソート済み配列のマージは $O(n)$ 時間しかかからない：2 つのポインタで両配列を走査し、常に小さい方の先頭要素を出力バッファにコピーする。

マージサブルーチン

再帰的なソーターを書く前に、マージステップを単独で構築する。隣接する 2 つのソート済みスライス left と right（共有するバッキング配列のサブスライス）と一時バッファを受け取り、マージ結果を元の位置に書き戻す。

fn merge(
    left: []i64,
    right: []i64,
    tmp: []i64,
) void {
    var i: usize = 0; // left へのインデックス
    var j: usize = 0; // right へのインデックス
    var k: usize = 0; // tmp へのインデックス

    // 片側が尽きるまで小さい方の先頭要素をコピーする。
    while (i < left.len and j < right.len) {
        if (left[i] <= right[j]) {
            tmp[k] = left[i];
            i += 1;
        } else {
            tmp[k] = right[j];
            j += 1;
        }
        k += 1;
    }

    // 残っている方の側を排出する。
    while (i < left.len) : (i += 1) {
        tmp[k] = left[i];
        k += 1;
    }
    while (j < right.len) : (j += 1) {
        tmp[k] = right[j];
        j += 1;
    }

    // マージ結果を元のメモリに書き戻す。
    // left と right は隣接しているのでこれで両方をカバーする。
    const full = left.len + right.len;
    for (0..full) |idx| {
        left.ptr[idx] = tmp[idx]; // idx >= left.len のとき left.ptr[idx] は right に達する
    }
}

ループ不変条件：最初の while のすべての反復の開始時に、tmp[0..k] は left と right からの $k$ 個の最小要素をソート順で保持している。どちらかのポインタがスライスの端に達すると、この不変条件は他方の残りの要素にも成り立つ — その側を排出することでソート順が保たれる。

再帰的なソーター

merge が準備できれば、再帰的な関数は短い：

fn mergeSort(arr: []i64, tmp: []i64) void {
    if (arr.len <= 1) return; // 基底ケース：既にソートされている

    const mid = arr.len / 2;
    mergeSort(arr[0..mid], tmp[0..mid]);
    mergeSort(arr[mid..], tmp[mid..]);
    merge(arr[0..mid], arr[mid..], tmp);
}

tmp は arr と同じ長さのバッファで、呼び出し元が一度確保してすべての再帰呼び出しに受け渡す。繰り返しのアロケーションを避けるためだ。

全体をまとめる

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var data = [_]i64{ 38, 27, 43, 3, 9, 82, 10 };
    const tmp = try allocator.alloc(i64, data.len);
    defer allocator.free(tmp);

    mergeSort(&data, tmp);

    const stdout = std.io.getStdOut().writer();
    for (data, 0..) |x, i| {
        if (i > 0) try stdout.writeByte(' ');
        try stdout.print("{d}", .{x});
    }
    try stdout.writeByte('\n');
    // 出力：3 9 10 27 38 43 82
}

正しさの証明

$n = \texttt{arr.len}$ に対する強帰納法による形式的な正しさの議論：

基底ケース ( $n \le 1$ )：関数は即座に return する。1 要素の配列は自明にソートされている。
帰納的ステップ： $n$ 未満のあらゆる長さの配列を mergeSort が正しくソートすると仮定する。両半分の長さは $\lfloor n/2 \rfloor \le n - 1 < n$ なので、帰納仮定により再帰呼び出し後にソートされる。merge 関数（上のループ不変条件で正しさが証明されている）が長さ $n$ のソート済み配列を生成する。

帰納法により、mergeSort はあらゆる長さの配列をソートする。

時間計算量の解析

$T(n)$ を長さ $n$ の配列に対する操作数とする。

T(n) = \begin{cases} O(1) & n \le 1 \\ 2\,T(n/2) + O(n) & n > 1 \end{cases}

$2\,T(n/2)$ の項が 2 つの再帰呼び出しを、 $O(n)$ の項が merge を表す。再帰木を展開すると：

レベル	部分問題数	各サイズ	レベルあたりの仕事
0	1	$n$	$O(n)$
1	2	$n/2$	$O(n)$
2	4	$n/4$	$O(n)$
$\vdots$	$\vdots$	$\vdots$	$\vdots$
$\log_2 n$	$n$	$1$	$O(n)$

$\log_2 n + 1$ レベルがあり、各レベルが $O(n)$ かかるので：

T(n) = O(n \log n).

この境界はタイトだ — マージソートは常に半分に分割し常に全幅でマージするので、最良・最悪・平均ケースはすべて $\Theta(n \log n)$ だ。

空間計算量

マージソートは一時バッファに $O(n)$ の余分な空間を使う。これがインプレースでない理由だ（ $O(1)$ の余分な空間でソートする選択ソートとは異なる）。メモリ制限のある環境での大きな配列には注目すべき点だ。

単純なソートとの比較

アルゴリズム	最悪ケース	最良ケース	余分な空間	安定
バブルソート	$\Theta(n^2)$	$\Theta(n)$	$O(1)$	はい
選択ソート	$\Theta(n^2)$	$\Theta(n^2)$	$O(1)$	いいえ
マージソート	$\Theta(n \log n)$	$\Theta(n \log n)$	$O(n)$	はい

安定とは等しい要素が入力と同じ相対順序で出力に現れることだ。マージソートは安定だ。left[i] <= right[j] の条件が同点を左側（早い方）の要素に有利に破るためだ。

まとめ

マージソートは配列を中点で分割し、各半分を再帰的にソートして結果をマージする。
マージステップは $O(n)$ で動作し、アルゴリズムのエンジンだ。
漸化式 $T(n) = 2T(n/2) + O(n)$ は再帰木を通じて $\Theta(n \log n)$ に解ける。
時間計算量はすべてのケースで $\Theta(n \log n)$ — 悪い入力がない。
代償は一時バッファの $O(n)$ 余分な空間で、インプレースではない。
マージソートは安定だ：等しい要素は元の相対順序を保つ。