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:

  1. Divide L into two pieces, its HEAD and its TAIL.
  2. recursively sort the TAIL.
  3. INSERT the HEAD into the sorted TAIL.
This is called Insertion Sort.

Example: Given L = [56,35,42,29]:

  1. HEAD = 56. TAIL = [35,42,29].
  2. Recursively sort the TAIL. Result = [29,35,42]. (the details of this step are given below)
  3. INSERT 56 into [29,35,42]. Result = [29,35,42,56].
Step (2) is a recursive call, so it follows the same pattern, except for this computation, L = [35,42,29].
  1. HEAD = 35. TAIL = [42,29].
  2. Recursively sort the TAIL. Result = [29,42].
  3. INSERT 35 into [29,42]. Result = [29,35,42].
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.