# 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.

(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:

(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.)