Insertion Sort

Insertion Sort works as follows:

1. Divide the given list into two parts: sorted and unsorted
2. Iterate over unsorted list and insert each element into the sorted list at a proper position
3. So the elements in the sorted list are always in order

Following diagram illustrates this method:

Pseudocode for Insertion Sort:

Insertion-Sort(LIST)

  for j = 2 to LIST.length
      key = LIST[j]
      // insert key into sorted sequence LIST[1 .. j-1]
      i = j - 1
      while i >= 0 and key < LIST[i]
          LIST[i + 1] = LIST[i]
          i = i - 1    
      LIST[i + 1] = key

And here is a Java implementation of Insertion sort algorithm:

public class InsertionSort {
public static void sort(int[] list) {
for (int j = 1; j < list.length; j++) {
int key = list[j];
int i = j - 1;
while (i >= 0 && key < list[i]) {
list[i + 1] = list[i];
i--;
}
list[i + 1] = key;
}
}
}

Worst case running time for insertion sort is quadratic i.e. O(n^2).
Best case (when the array is already sorted) running time is linear i.e. O(n).

Space complexity for insertion sort is O(1) i.e. it requires constant amount of extra storage, in this case only one temporary variable which is "key".

Insertion sort is often a choice when the list is nearly sorted or when the list size small. Insertion is stable because it maintains the order of items which are equal.