Summary

In this chapter, we discussed divide and conquer in two different ways: first as an algorithm design paradigm, and then its use in designing other tools that help us in scaling our software. We covered some standard divide-and-conquer algorithms (merge sort and quicksort). We also saw how simple operations such as partition underlie the solutions to different problems such as partial sorting and linear time selection.

An important idea to keep in mind while implementing these algorithms in practice is the separation of data structures that hold data from the implementation of the algorithm itself. Using C++ templates is often a good way to achieve this separation. We saw that the C++ Standard Library comes with a large set of primitives that can be used for implementing divide-and-conquer algorithms.

The simplicity of the underlying idea behind divide and conquer makes it an incredibly useful tool in solving problems and allows for the creation of parallelization frameworks such as...