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

If L has zero or one element, then it is already sorted, so nothing need be done;
Otherwise
1. divide in L into two smaller lists, L1 and L2.
2. recursively sort each of the smaller lists. Result: L1 and L2 are now sorted.
3. Combine L1 and L2. The result is a sorted version of the original list. How do we combine L1 and L2? As just discussed there's only one way to do so and produce a sorted list. We MERGE them.

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.