Insertion Sort

Pseudocode

Analysis

• Best case: list is already sorted, number of comparisons is $(n − 1)$
• Worst case: reversed list; each iteration shifts the element all the way down
• First iteration: 1 comparison, 2nd: at most 2, etc., last iteration: at most $(n − 1)$
comparisons $$\sum_{i=1}^{n-1}i=\frac{n(n-1)}{2} $$
• Worst case: $O(n^2)$
• A more complex analysis for the average case, but still $O(n^2)$
• Practical consideration: insertion sort is inherently adaptive; good performance in
practice
• Very efficient on small lists, especially if there is already some structure (partially
ordered) to them

Code Samples

Code Sample 13: Java Insertion Sort for integers

public static void insertionSort (int array []) {
  int value ;
  for (int i =1; i < array . length ; i ++) {
    value = array [ i ];
    int j = i ;
      while ( j > 0 && array [j -1] > value ) {
      array [ j ] = array [j -1];
      j - -;
    }
    array [ j ] = value ;
  }
}

Code Sample 14: C Insertion Sort for integers

void insertionSort (int * array , int size ) {
  int value ;
  for (int i =1; i < size ; i ++) {
    value = array [ i ];
    int j = i ;
    while ( j > 0 && array [j -1] > value ) {
      array [ j ] = array [j -1];
      j - -;
    }
    array [ j ] = value ;
  }
}