6.15.1. Recursive Sorting¶

In looking for a recursive solution, you should first discover what characteristics of sorting make it a recursive problem. In order for any problem to be solved recursively it must satisfy:

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 these smaller parts.

3- We must be able to determine a set of simple cases which can be solved diectly, without any further decomposition.

The next exercises will ask you to implement variations of merge sort.