# Divide-and-conquer

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

## Introduction

Divide-and-conquer algorithms involve three steps:

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

[1, P. 65]

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. [1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. The MIT Press, 2009.