### Insertion Sort

 home  Bib Algorithms Bioinfo FP Logic MML Prog.Lang and the mmlist

Algorithms
glossary
Sorting
Insertion
Quick
Merge
Heap
Dutch N.F.

Insertion sort maintains a sorted front section of the array [1..i-1]. At each stage, a[i] is inserted at the appropriate point in this sorted section and i is increased.

```insertion(int a[], int N)  /* in C */
/* sort a[1..N],  NB. 1 to N */
{ int i, j, ai;
a = -MAXINT; /* a sentinel */

for(i=2; i <= N; i++)
{ /* invariant: a[1..i-1] sorted */
ai = a[i];
j = i-1;
while( a[j] > ai )
{ /* invariant: a[j+2..i] > ai */
a[j+1] = a[j];
j--;
}
/* a[1..j] <= ai < a[j+2..i] */

a[j+1] = ai;
/* a[1..i] is sorted */
}
}/*insertion*/
```

Part way through sorting, a[1..i-1] is sorted. Consider a[i], and how to insert it into a[1..i-1] so as to make a[1..i] sorted:

```
sorted
----------
a:  1  2  3  6  5  4
^
|
|
i

```

Examine the elements a[i-1], a[i-2], ..., a, moving each of them one place right, and stopping when an element less than or equal to (the original) a[i] is found, or at the left-hand end of the array if no such element is found.

```          ai=5

a:  1  2  3  -  6  4
^
|
i

```

Place the original a[i] in the vacant location:

```
sorted
-------------
a:  1  2  3  5  6  4
^
|
i

```

Now a[1..i] is sorted. Repeat until i=N.

### Insertion Sort Demonstration

Change the data in the HTML FORM below, click `go', and experiment. The sorted section of the array is [bracketted] in the trace area:

input:
output:
trace:

### Complexity

#### Time

The number of comparisons of elements in the worst case is

```  (N-1) + (N-2) + ... + 1
= (N-1)*N/2
```
i.e. O(N2).

The average case time-complexity is O((N-1)*N/4), i.e. O(N2).

The best-case time complexity is when the array is already sorted, and is O(N).

#### Space

The space-complexity is O(1), just a few scalar variables.

### Stability

Insertion sort is stable, i.e. the relative order of equal keys is not changed, provided that you are careful about scanning the sorted region from right to left.

### Notes

• The way that elements of the array are `moved up' in insertion sort, a[j+1]:=a[j], involves just one assignment against three for an exchange in selection sort.
• If you are sorting non-numeric data, there might not be a convenient `-maximum value' to use as a sentinel and you will have to ensure that the inner loop terminates, in the case that `ai' is the least element in the data, by some other means.