Insertion Sort

Internal

• Data Structures and Algorithms
• Sorting Algorithms

Overview

Insertion sort is a key comparison algorithm that receives an array of integers and sorts the values in-place. It is an efficient algorithm for sorting a small number of elements. The insertion sort has an average-case running time of Θ(n²), as its time-complexity analysis demonstrates.

Algorithm

Insertion sort works as follows: we start from the left side of the array, and for each key, we insert it in the correct position in the already sorted sub-array that grows from left to right. The insertion is performed by scanning the sub-array from right to left in a while loop and swapping the elements until we reach the correct position of the key being handled.

public static void insertionSort(int[] a) {

  //
  // handle trivial cases when the array is empty or has just one element
  //

  //
  // going forward, we assume the array has at least two elements
  //

  for(int i = 1; i < a.length; i ++) {

    //
    // if larger or equal, the key is in the right position, advance in the top level loop.
    // This test is not strictly necessary, as the lower loop will take care of this case
    // also, it was introduced here for clarity
    //

    if (a[i] >= a[i - 1]) {
      continue;
    }

    //
    // The key is smaller than the last one in the sorted subarray, 
    // send it through the subarray until it reaches the correct position.
    // Use a different index variable.

    int j = i - 1; // this is the first element of the sorted subarray

    //
    // order in which comparison expressions are evaluated is important, 
    // we use short-circuiting if j is negative
    //
    while(j >= 0 && a[j] > a[j + 1]) {

      int key = a[j + 1];
      a[j + 1] = a[j];
      a[j] = key;
      j --;
   
    }
  }
}

Time Complexity Analysis

In performing the time complexity analysis of the insertion sort, we use the conventions and assumptions described in the Algorithm Complexity section.

TODO CLRS page 24.