Insertion Sort

Internal

• 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.

Worst-case time	Θ(n2)
Average-case time	Θ(n2)
Best-case time	Ω(n)

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.

Discussion

In what cases is insertion sort better than Quicksort or Merge Sort?