## Revisiting Sorting Algorithms

Remember selection sort and insersion sort? These simple sorting algorithms are convenient to use when sorting a small amount of data. However, their runtime complexity is O(n^{2}), which makes them very slow when sorting a lot of data. Can we sort more efficiently? Take a look at the following list of *n* integers. Can you think of a way to sort them faster than O(n^{2})?

[45, 31, 5, 12, 8, 67, 9, 20, 22]

We have used the divide and conquer strategy to make searching faster.

**Divide** the problem into two or more smaller subproblems of the same or related type. **Conquer** the subproblems by solving them recursively, until these become simple enough to be solved directly as base cases. **Combine** the solutions to the subproblems into the solution for the original problem.

Can we use divide and conquer in sorting? Think of it for a moment before moving to the next page.