1. General Sorting Strategy (Recursive)

A sorting algorithm is an algorithm whose input is any list and whose output is a list (or a change in the given list) that is sorted and has the same elements as the given list.

Most well-known sorting algorithms are based on this general strategy: given a list L

This strategy works no matter how we do step (1). The pieces can be any size; they could be the same size, or they could be very different sizes; and it does not matter which elements of L we put together or in what order we put them into the pieces. We can divide up and scramble up the elements any way we like, and we will still sort L. In fact, we could even divide L into more than two pieces, we could divide it into 3, or 7, or whatever.

The one thing we must avoid is having one of the pieces equal to L; if this happens we would have an infinite loop. But that is the only thing we have to avoid.

We will now look at three specific versions of this general strategy: Merge Sort, Insertion Sort and Quick Sort.