Insertion Sort

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:

input:  
output:
trace:  

©
L
.
A
l
l
i
s
o
n

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

L.A. ©