Recursive MergeSort

Instead of dividing the list once, a recursive mergeSort will keep dividing the list in half until the sublists are one or two values in length.

When developing a recursive solution, a key step is identifying the base case of the solution. What situation will terminate the recursion? In this case, a sublist of one or two values will be our two base cases.

Let's try and work through the recursive mergeSort of a list of eight values.

• The list is divided into two sublists:

• Now let's work on the left sublist. It will be divided into lists of two.

• Each list of two is now very easy to sort. After each list of two is sorted, we then merge these two lists back into a list of four.

• Now the algorithm proceeds to solve the right sublist (positions 5-8) recursively. Then the two lists of four are merged back together.