3. Insertion Sort
In order to use INSERT instead of MERGE it is clear what we have to
do. We have to divide L so that one of the pieces is a singleton. This
is easy - for example, just separate the head of L from its tail.
Knowing that this piece is a singleton, we also can delete the
recursive call that sorts it. This leads to the algorithm:
This is called Insertion Sort.
- Divide L into two pieces, its HEAD and its TAIL.
- recursively sort the TAIL.
- INSERT the HEAD into the sorted TAIL.
Given L = [56,35,42,29]:
Step (2) is a recursive call, so it follows the same pattern, except
for this computation, L = [35,42,29].
- HEAD = 56. TAIL = [35,42,29].
- Recursively sort the TAIL. Result = [29,35,42]. (the details of
this step are given below)
- INSERT 56 into [29,35,42]. Result = [29,35,42,56].
So, we have succeeded in replacing the MERGE operation in step (3)
with an INSERT operation, which is quite a bit more efficient.
However, we have made a major sacrifice in efficiency in order to do
this. Merge Sort happens to be one of the fastest sorting
algorithms known; its speed is entirely due to the fact that it cuts
the given list L into two equal size pieces. Insertion Sort gives up
this source of efficiency, and as a result, it is much less efficient
for large lists. We will see how to analyze the efficiency of
algorithms later in the lecture.
- HEAD = 35. TAIL = [42,29].
- Recursively sort the TAIL. Result = [29,42].
- INSERT 35 into [29,42]. Result = [29,35,42].