# Divide-and-conquer

“Veni, vidi, vici. (I came, I saw, I conquered.)”― Julius Caesar

## Table of contents

## Introduction

Divide-and-conquer algorithms involve three steps:

**Divide**the problem into smaller subproblems.**Conquer**the subproblems by solving them recursively.**Combine**the solutions to the subproblems into the solution for the original problem.

When a subproblem is large enough to be solved recursively, it’s called the **recursive case** [1, P. 65].

When a subproblem becomes small enough that the algorithm no longer recurses (the recursion “bottoms out”), it is called the **base case** [1, P. 65].

Merge sort is an example of a divide-and-conquer algorithm.

## References

- [1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,
*Introduction to Algorithms*, 3rd ed. The MIT Press, 2009.