Thinking Recursively with Java

7.2. Merge Sorting

The first step in looking for a recursive solution to the sorting problem is discovering what characteristics of sorting might make it appropriate for recursive strategies. To do so, it helps to review the conditions required for applying a recursive technique:

1. There must be some way to break large problems down into simpler instances of the same problem.

2. Assuming that each of those subproblems can be solved by successive applications of the recursive procedure, there must be some way to generate a solution to the original problem from the solution to each of the smaller parts.

3. It must be possible to identify a set of simple cases that can be solved directly, without any further decomposition.

How well do these conditions apply to sorting?

In seeking a recursive solution, it often helps to identify the simple cases first. Given that the problem is sorting an array of size N, the easiest cases are when N = 1, or even easier, when N = 0. In either case—an array with a single element or one with no elements—the array must already be sorted. Thus, in a recursive algorithm for sorting, the simple cases require no work at all.

Now that the simple cases are out of the way, it is appropriate to return to the more complicated task of finding a recursive subdivision. You can break up a large array into smaller ones in a variety of different ways. In seeking to reduce the computational complexity of an algorithm, however, it often helps to divide the problem into subproblems ...