Divide and Conquer

Introduction

Divide and Conquer is an algorithmic technique in which we solve a problem by splitting it into smaller subproblems, solving those subproblems recursively, and then combining their answers.

A typical divide-and-conquer algorithm follows three main steps:

Divide — split the problem into smaller subproblems;
Conquer — solve the subproblems recursively;
Combine — merge the subproblem answers into the final answer.

This idea appears in many important algorithms.

Merge Sort

Statement

Given an array

a_1, a_2, \ldots, a_n

Divide and Conquer

Introduction

Merge Sort

Statement

External Problems

Solution

Implementation