8.1.2 Insertion Sort

The list-sort-best-first procedure seems quite inefficient. For every output element, we are searching the whole remaining list to find the best element, but do nothing of value with all the comparisons that were done to find the best element.

An alternate approach is to build up a sorted list as we go through the elements. Insertion sort works by putting the first element in the list in the right place in the list that results from sorting the rest of the elements.

First, we define the list-insert-one procedure that takes three inputs: a comparison procedure, an element, and a List. The input List must be sorted according to the comparison function. As output, list-insert-one produces a List consisting of the elements of the input List, with the input element inserts in the right place according to the comparison function.

(define (list-insert-one cf el p) ; requires: p is sorted by cf
  (if (null? p) (list el)
      (if (cf el (car p)) (cons el p)
          (cons (car p) (list-insert-one cf el (cdr p))))))

The running time for list-insert-one is in $\Theta(n)$ where $n$ is the number of elements in the input list. In the worst case, the input element belongs at the end of the list and it makes $n$ recursive applications of list-insert-one. Each application involves constant work so the overall running time of list-insert-one is in $\Theta(n)$.

To sort the whole list, we insert each element into the list that results from sorting the rest of the elements:

(define (list-sort-insert cf p)
  (if (null? p) null
      (list-insert-one cf (car p) (list-sort-insert cf (cdr p)))))

Evaluating an application of list-sort-insert on a list of length $n$ involves $n$ recursive applications. The lengths of the input lists in the recursive applications are $n-1$, $n-2$, $\ldots$, 0. Each application involves an application of list-insert-one which has linear running time. The average length of the input list over all the applications is approximately $\frac{n}{2}$, so the average running time of the list-insert-one applications is in $\Theta(n)$. There are $n$ applications of \scheme|list-insert-one|, so the total running time is in $\Theta(n^2)$.

Exercise 8.5. We analyzed the worst case running time of list-sort-insert above. Analyze the best case running time. Your analysis should identify the inputs for which list-sort-insert runs fastest, and describe the asymptotic running time for the best case input.

Exercise 8.6. Both the list-sort-best-first-sort and list-sort-insert procedures have asymptotic running times in $\Theta(n^2)$. This tells us how their worst case running times grow with the size of the input, but isn't enough to know which procedure is faster for a particular input. For the questions below, use both analytical and empirical analysis to provide a convincing answer.
a. How do the actual running times of list-sort-best-first-sort and list-sort-insert on typical inputs compare?
b. Are there any inputs for which list-sort-best-first is faster than list-sort-insert?
c. For sorting a long list of $n$ random elements, how long does each procedure take? (See Exercise 8.2 for how to create a list of random elements.)