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.
- If L has zero or one element, then it is already sorted, so
nothing need be done;
- 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.
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.