insertion sort

The Problem

See the sorting problem.

The Algorithm

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

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

Since at step $i$, the length of list $L^{\prime }$ is $i$ and the length of list $L$ is $n-i$, we can implement thisalgorithm 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
         for $i\leftarrow 1\text{ to }n$ do

begin

$value\leftarrow L[i]$

$position\leftarrow Binary\mathrm{\_}Search(L,1,i,value)$

for $j\leftarrow i\text{ downto }position$ do

$L[j]\leftarrow L[j-1]$

$L[position]\leftarrow value$

end
end

function Binary_Search(L, bottom, top, key)
begin
         if $bottom\ge top$ then

$Binary\mathrm{\_}Search\leftarrow bottom$

else

begin

$middle\leftarrow (bottom+top)/2$

if then

$Binary\mathrm{\_}Search\leftarrow Binary\mathrm{\_}Search(L,bottom,middle-1,key)$

else

$Binary\mathrm{\_}Search\leftarrow Binary\mathrm{\_}Search(L,middle+1,top,key)$

end
end

Analysis

In the worst case, each step $i$ requires a shift of $i-1$ elements for the insertion (consider an inputlist that is sorted in reverse order). Thus the runtime complexity is $𝒪(n^2)$. Even the optimizationof 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 $𝒪(\log n)$ insertion time, giving $𝒪(n\log n)$ runtime,but then the algorithm can no longer be done as an in-place sorting algorithm. Such data structures are also quitecomplicated.

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