The Problem

See the sorting problem.

The Algorithm

Suppose $L = \left\{ x_1, x_2, \dots, x_n\right\}$ is the initial list of unsorted elements. The insertion sort algorithm will construct a new list, containing the elements of $L$ in order, which we will call $L'$ . The algorithm constructs this list one element at a time.

Initially $L'$ is empty. We then take the first element of $L$ and put it in $L'$ . We then take the second element of $L$ and also add it to $L'$ , placing it before any elements in $L'$ that should come after it. This is done one element at a time until all $n$ elements of $L$ are in $L'$ , in sorted order. Thus, each step $i$ consists of looking up the position in $L'$ where the element $x_i$ should be placed and inserting it there (hence the name of the algorithm). This requires a search, and then the shifting of all the elements in $L'$ that come after $x_i$ (if $L'$ is stored in an array). If storage is in an array, then the binary search algorithm can be used to quickly find $x_i$ 's new position in $L'$ .

Since at step $i$ , the length of list $L'$ is $i$ and the length of list $L$ is $n - i$ , we can implement this algorithm as an in-place sorting algorithm. Each step $i$ results in $L[1..i]$ becoming fully sorted.

Pseudocode

This algorithm uses a modified binary search algorithm to find the position in $L$ where an element $key$ should be placed to maintain ordering.

Algorithm INSERTION_SORT(L, n)
Input: A list $L$ of $n$ elements
Output: The list $L$ in sorted order

begin
$i \gets 1\mbox{ to }n$ \textbf{do}\\ \hspace*{0.... ...\hspace*{0.4in}\parbox{\textwidth}{$L[j] \gets L[j - 1]$ } \\ $L[position] \gets value$ }\\ \textbf{end}} }$">
end

function Binary_Search(L, bottom, top, key)
begin
$bottom >= top$ \textbf{then}\\ \hspace*{0... ...extbf{else}\\ \hspace*{0.4in}\parbox{\textwidth}{$Binary\_Search \gets Binary\_Search(L, middle + 1, top, key)$ } }\\ \textbf{end}} }$">
end

Analysis

In the worst case, each step $i$ requires a shift of $i - 1$ elements for the insertion (consider an input list that is sorted in reverse order). Thus the runtime complexity is $\mathcal{O}(n^2)$ . Even the optimization of using a binary search does not help us here, because the deciding factor in this case is the insertion. It is possible to use a data type with $\mathcal{O}(\log{n})$ insertion time, giving $\mathcal{O}(n\log{n})$ runtime, but then the algorithm can no longer be done as an in-place sorting algorithm. Such data structures are also quite complicated.

A similar algorithm to the insertion sort is the selection sort, which requires fewer data movements than the insertion sort, but requires more comparisons.