### Insertion Sort

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

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[0] = -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[1], 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:

 ©L.Allison
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.

L.A. ©
Department of Computer Science UWA 1984, Department of Computer Science Monash 1986, and (HTML) School of Comp. Sci. & Software Engineering, Monash University 1999
window on the wide world:
 The Darwin Awards V: Next Evolution

 Linux  Ubuntu free op. sys. OpenOffice free office suite, ver 3.4+ The GIMP ~ free photoshop Firefox web browser FlashBlock like it says!

 © L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated), Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University, was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.) Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Thursday, 29-Sep-2016 08:12:14 EST.