分割統治法とは？高速なソートアルゴリズム【ソートアルゴリズム入門】#5

O[n²] の壁

こんにちは！以前の記事でバブルソートや挿入ソートなどの単純なソートアルゴリズムと、その計算量が O[n² ]になることを学びました。

では、エンジニアたちはこの O[n²] の壁をどうやって乗り越えたのでしょうか？

その答えが、今回紹介する分割統治法 (Divide and Conquer)という強力な問題解決の「戦略」です。

この記事では、マージソートやクイックソートといった高速なアルゴリズムの根幹をなす「分割統治法」の考え方について、図を使いながら分かりやすく解説します。

分割統治法とは？

分割統治法とは、その名の通り、 「大きな問題を、そのまま解くのが難しいなら、小さな問題に”分割”して、それぞれを”統治”（解決）し、最後にその結果をうまいこと”結合”して、元の問題の答えを導く」 という手法です。

【身近な例】 あなたが「1000ページある本」を校正（誤字脱字チェック）する担当者だとします。

方法は？

• 悪い方法（O[N]的）: 1ページ目から1000ページ目まで、一人で全部やろうとします。疲れてくると効率が落ち、ミスも増えます。（これは例えですが）
• 分割統治法:
  1. 分割: 1000ページの本を、「100ページずつの束」10個に分けます。
  2. 統治: 10人のアルバイトを雇い、それぞれに100ページずつの束を渡して校正してもらいます。（これが「解ける最小単位」の問題）
  3. 結合: 10人から返ってきた校正済みの束を、順番通りにまとめて、1冊の「校正済み1000ページの本」として完成させます。

一人でやるより、圧倒的に速く終わりそうですよね？ アルゴリズムの世界でも、これと全く同じことを行います。

分割統治法の3つのステップ

分割統治法は、基本的に以下の3つのステップで構成されます。

1. 分割 (Divide)

大きな問題を、より小さな（そして同じ種類の）複数の部分問題に分割します。再帰的に（自分自身を呼び出すように）問題をどんどん小さくしていくのが特徴です。

• 例: 8つの要素のソートなら、4つの要素のソート×2 に分割します。
• その4つの要素のソートも、さらに 2つの要素のソート×2 に分割します。
• 最終的に「要素が1つ」になるまで分割します。（要素1つは、すでにソート済みとみなせます）

2. 統治 (Conquer)

分割された部分問題が、もうそれ以上分割できない「最小単位」まで来たら、その問題を直接解きます。

（ソートの例で言えば、「要素が1つ」になった瞬間がこれにあたります。要素が1つなら、何もしなくてOKです）

3. 結合 (Combine)

「統治」ステップで得られた部分問題の「解」を、今度は逆に組み合わせて（マージして）、元の問題の「解」を導き出します。

• 例: 「ソート済みの2つの要素」と「ソート済みの2つの要素」を合体させて、「ソート済みの4つの要素」を作ります。
• 「ソート済みの4つの要素」と「ソート済みの4つの要素」を合体させて、「ソート済みの8つの要素」を完成させます。

重要なのは、この「結合」のステップをいかに効率よく行うかです。

なぜ O[n²]から O[n log n] に高速化できるのか？

「結局、全部の要素を扱っているんだから、作業量は同じでは？」と思うかもしれません。

これが分割統治法のスゴいところです。

分割統治法と単純ソートの違い

以前の記事で紹介した単純ソートを思い返してみて下さい、

• 選択ソートでは、未ソート部分の要素を毎回比較して最大値を探していました、

• 挿入ソートでは、未ソートな要素をどこに挿入すべきか？未ソート部分の要素を毎回比較して挿入位置を探していました。

• バブルソートでは、同じく未ソート部分の要素を毎回比較して交換を行っていました。

この未ソート部分の要素を毎回比較をさせないというのが分割統治法が早い理由です。

分割統治法（を使ったマージソートなど）では、この「未ソート部分の要素を毎回比較(総当たり)」をさせません。

• 分割のステップは、データを「半分に、半分に」と分けていきます。
  • 8個のデータなら、8→4→2→1 と、たった3回で最小単位に到達します。
  • 100万個のデータでも、たった20回ほどで到達します。
  • この「半分にできる回数」こそが、次の記事で解説する log n の正体です。
• 結合のステップは、賢いやり方（マージソートで詳しく解説します）を使えば、およそ $N$ 回の比較・移動で済みます。

結果として、「log n 回のレベル（深さ）」と「各レベルでの作業量 n」を掛け合わせた、

O[n log n]

という、 O[n²] とは比べ物にならない驚異的な速さを実現できるのです。

まとめ：高速アルゴリズムへの「設計思想」

今回は、マージソートやクイックソートといった高速な O[n log n] アルゴリズムの土台となる「分割統治法」という戦略（設計思想）について解説しました。

• 分割統治法は「分割」「統治」「結合」の3ステップで問題を解く戦略。
• 大きな問題を再帰的に小さくしていく。
• O[n²] の「総当たり」を避け、O[n log n] という高速化を可能にする。

この「賢い考え方」を理解した上で、次回はついに、この分割統治法を最も素直に実装したアルゴリズム「マージソート」の具体的な仕組みを見ていきましょう！

マージソートの仕組みを徹底解説！アニメーションで学ぶ「分割統治」ソート・併合ソート【ソートアルゴリズム入門】#6

「マージソート」は「分割統治法」に基づく高速なソートです。O(N^2)の単純ソートとは異なり、O(N log N)の計算量を実現します。データを半分に「分割」し、ソートしながら賢く「結合（マージ）」する仕組みを図解します。