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²), 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²)?

[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.