分割統治法とは
分割統治法とは、そのままでは解決するのが難しい大きな問題を、いくつかの「扱いやすい小さな問題」に細かく分割し、それぞれの小さな問題を個別に解決（統治）してから、最後にその結果を組み合わせて元の大きな問題の答えを導き出す手法です。
このアプローチはアルゴリズム設計の基本であり、特にデータを並び替える「ソート」や、データを検索する処理でよく使われます。問題を細かく分割するプロセスは、これ以上分割できない最小単位になるまで再帰的（繰り返し）に続けられ、小さな問題を一瞬で解いてから、ドミノ倒しのように組み上げていきます。
具体例
バラバラに置かれた8枚のカードを数字の小さい順に並べ替える（ソートする）場面を考えます。分割統治法（マージソート）では、まず8枚を4枚ずつの2グループに分け、さらに2枚ずつ、最終的に1枚ずつの8グループに分解します。1枚ずつのグループはすでに整列しているとみなせるため、隣り合うグループ同士を「小さい順になるように合流（マージ）」させながら、2枚、4枚、8枚と組み立て直すことで効率よく並べ替えを完了します。
もう少し詳しく
分割統治法の利点は、複雑な問題を機械的な単純作業に落とし込める点と、並列処理との相性が非常に良い点にあります。分割されたそれぞれの小さな問題は、お互いに独立しているため、マルチコアのCPUや複数のコンピュータを用いて同時に並行して計算（統治）することが可能です。分割統治法を設計する際は、通常3つのステップを踏みます。1つ目は「分割（Divide）」で、問題を同じ形式のより小さなサブ問題に分割します。2つ目は「統治（Conquer）」で、サブ問題を再帰的に解決します（十分に小さければ直接解きます）。3つ目は「結合（Combine）」で、サブ問題の解を組み合わせて元の問題の解を構築します。この手法により、効率的なアルゴリズムが数多く開発され、情報科学の発展に大きく貢献しました。
試験でのポイント
シラバスや試験では、分割統治法を応用した具体的なアルゴリズムとその動作手順が問われます。最も代表的なのが、ソートアルゴリズムである「マージソート」と「クイックソート」、および探索アルゴリズムである「二分探索」です。これらのアルゴリズムがどのようにデータを分割し、どのような時間計算量（例：マージソートは常にO(N log N)）で動作するのかを理解しておく必要があります。また、動的計画法との最大の違いについてもよく問われます。動的計画法は「分割した子問題が重複しており、結果を再利用する」のに対し、分割統治法は「分割した子問題が互いに独立しており、結果の再利用を行わない」という点をしっかり整理しておきましょう。
関連する用語
分割統治法に関連するアルゴリズムとしては、データを中間位置で分割してソートする「マージソート」や、基準値（ピボット）を元に分割する「クイックソート」があります。また、範囲を半分に狭めていく「二分探索」や、分割した独立な問題を同時に処理する「並列プログラミング（マルチスレッド処理）」、そして比較対照となるアルゴリズム手法である「動的計画法」も重要な関連用語です。