Skip to content

Insertion Sort

This page gives a brief introduction to insertion sort.

Definition

Insertion sort is a simple, intuitive sorting algorithm. It splits the elements to be sorted into a "sorted" part and an "unsorted" part, and repeatedly picks one of the unsorted elements and inserts it at its correct position among the sorted ones.

Playing cards works the same way: you draw a card from the table, insert it into your hand according to its rank, and then draw the next card.

insertion sort animate example

Properties

Stability

Insertion sort is a stable sorting algorithm.

Time complexity

The best-case time complexity of insertion sort is \(O(n)\), and it is very efficient when the sequence is almost sorted.

Its worst-case time complexity and average-case time complexity are both \(O(n^2)\).

Implementation

Pseudocode

\[ \begin{array}{ll} 1 & \textbf{Input. } \text{An array } A \text{ consisting of }n\text{ elements.} \\ 2 & \textbf{Output. } A\text{ will be sorted in nondecreasing order stably.} \\ 3 & \textbf{Method. } \\ 4 & \textbf{for } i\gets 2\textbf{ to }n\\ 5 & \qquad \textit{key}\gets A[i]\\ 6 & \qquad j\gets i-1\\ 7 & \qquad\textbf{while }j>0\textbf{ and }A[j]>\textit{key}\\ 8 & \qquad\qquad A[j + 1]\gets A[j]\\ 9 & \qquad\qquad j\gets j - 1\\ 10 & \qquad A[j + 1]\gets \textit{key} \end{array} \]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void insertion_sort(int arr[], int len) {
  for (int i = 1; i < len; ++i) {
    int key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
}
1
2
3
4
5
6
7
8
def insertion_sort(arr, n):
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Binary insertion sort

Insertion sort can also be sped up with binary search. The gain is quite noticeable when there are many elements to sort.

Time complexity

Binary insertion sort finds each insertion position by binary search, which brings the total number of comparisons down to \(O(n\log n)\). In the worst case it still has to move \(\Theta(n^2)\) elements, though, so its worst-case time complexity is still \(\Theta(n^2)\).

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void insertion_sort(int arr[], int len) {
  if (len < 2) return;
  for (int i = 1; i != len; ++i) {
    int key = arr[i];
    auto index = upper_bound(arr, arr + i, key) - arr;
    // Move the elements with memmove: faster than a for loop, but still O(n) time
    memmove(arr + index + 1, arr + index, (i - index) * sizeof(int));
    arr[index] = key;
  }
}