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
- divide in L into two smaller lists, L1 and L2.
- recursively sort each of the smaller lists. Result: L1 and
L2 are now sorted.
- 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.

- divide in L into two smaller lists, L1 and L2.

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.