Perhaps the most difficult part of our process for writing algorithms is splitting a problem into subproblems. This is more an art than a science — there’s no systematic way to identify subproblems, and each problem might be split into subproblems in many different ways.(1)
In the previous post we saw two iterative sorting algorithms: selection sort and insertion sort both work using a loop to put the right values in the right places, one at a time. They are two of the simplest sorting algorithms. But they’re not very efficient — for long lists, they’re too slow.(1)
In this post we’ll see one of the simplest efficient sorting algorithms, called merge sort. Rather than sorting items one-by-one, it works by recursively sorting shorter lists.