マージソート（Merge Sort）の基本概念

マージソートは、分割統治法（Divide and Conquer）に基づいた効率的なソートアルゴリズムです。主な特徴は以下の通りです。

• 再帰的な構造：配列を半分に分割し、それぞれをソートした後にマージ（結合）します。
• 外部ソート：マージの過程で一時的な配列を使用し、順序を整えます。
• 安定ソート：同じ値の要素の相対的な順序が維持されます。

計算量とマスター定理

マージソートの計算量はマスター定理を用いて以下のように表されます：

T(N) = 2 * T(N/2) + O(N)

• 時間効率： O(N log N)
• 空間効率： O(N)（マージの際に要素数分の作業領域が必要なため）

配列による実装コード

public static void sort(int[] nums, int start, int end) {
    if (start == end) {
        return;
    }
    int middle = start + ((end - start) >> 1);
    sort(nums, start, middle);
    sort(nums, middle + 1, end);
    merge(nums, start, middle, end);
}

private static void merge(int[] data, int low, int mid, int high) {
    int[] helper = new int[high - low + 1];
    int i = 0;
    int leftPtr = low;
    int rightPtr = mid + 1;

    while (leftPtr <= mid && rightPtr <= high) {
        helper[i++] = data[leftPtr] <= data[rightPtr] ? data[leftPtr++] : data[rightPtr++];
    }

    while (leftPtr <= mid) {
        helper[i++] = data[leftPtr++];
    }
    while (rightPtr <= high) {
        helper[i++] = data[rightPtr++];
    }

    for (int j = 0; j < helper.length; j++) {
        data[low + j] = helper[j];
    }
}

応用例：小和問題（Small Sum Problem）

配列の各要素について、その要素より左側にあり、かつその要素より小さい値の合計を「小和」と呼びます。配列全体の小和を求める問題です。

例：[1, 3, 4, 2, 5] の場合
1の左側：なし（0）
3の左側：1
4の左側：1, 3
2の左側：1
5の左側：1, 3, 4, 2
合計：1 + (1+3) + 1 + (1+3+4+2) = 16

実装のポイント

マージの際、左側のグループの要素 data[leftPtr] が右側のグループの要素 data[rightPtr] より小さい場合、右側の残りすべての要素（high - rightPtr + 1 個）に対して data[leftPtr] が小和として加算されることを利用します。

public static int getSmallSum(int[] arr, int l, int r) {
    if (l == r) return 0;
    int m = l + ((r - l) >> 1);
    return getSmallSum(arr, l, m) + getSmallSum(arr, m + 1, r) + mergeSum(arr, l, m, r);
}

private static int mergeSum(int[] arr, int l, int m, int r) {
    int[] cache = new int[r - l + 1];
    int idx = 0;
    int pL = l;
    int pR = m + 1;
    int total = 0;

    while (pL <= m && pR <= r) {
        // 左側が小さい場合、右側にある個数分だけ加算
        total += arr[pL] < arr[pR] ? (r - pR + 1) * arr[pL] : 0;
        cache[idx++] = arr[pL] < arr[pR] ? arr[pL++] : arr[pR++];
    }
    while (pL <= m) cache[idx++] = arr[pL++];
    while (pR <= r) cache[idx++] = arr[pR++];

    for (int i = 0; i < cache.length; i++) {
        arr[l + i] = cache[i];
    }
    return total;
}

応用例：逆序対（Inversion Pair）

左側の要素が右側の要素よりも大きいペア (a[i], a[j]) where i < j を探します。マージソートの降順ソート、または昇順マージの際の比較ロジックを応用してカウント可能です。

連結リストのソート

連結リストにおけるマージソートは、ランダムアクセスができない性質上、配列よりも空間計算量を抑えて実装できる場合があります。以下は ListNode を用いた実装例です。

class ListSorter {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode mid = findMiddleNode(head);
        ListNode rightHead = mid.next;
        mid.next = null; // リストを分割

        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);

        return mergeLists(left, right);
    }

    private ListNode findMiddleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode mergeLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        current.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}