Insertion Sort

LA home
Computing
 Algorithms
 Bioinformatics
 FP,  λ
 Logic,  π
 MML
 Prog.Langs

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
.
A
l
l
i
s
o
n
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:

Computer Science Education Week

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 Sunday, 26-Oct-2014 15:24:23 EST.