Insertion Sort

This page briefly introduces insertion sort.

Definition

Insertion sort (English: Insertion sort) is a simple and intuitive sorting algorithm. Its principle is to divide the elements to be sorted into two parts, "sorted" and "unsorted", and each time select an element from the "unsorted" elements and insert it into the correct position among the "sorted" elements.

An operation equivalent to insertion sort is drawing a playing card from the table, inserting it into your hand according to the card's rank, and then drawing the next card.

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 highly efficient when the sequence is nearly sorted.

The worst-case and average-case time complexities of insertion sort are both $O(n^2)$.

Code 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 key\gets A[i]\\ 6 & \qquad j\gets i-1\\ 7 & \qquad\textbf{while }j>0\textbf{ and }A[j]>key\\ 8 & \qquad\qquad A[j + 1]\gets A[j]\\ 9 & \qquad\qquad j\gets j - 1\\ 10 & \qquad A[j + 1]\gets key \end{array}$$

C++

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;
  }
}

Python

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

Java

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 have its performance optimized using a binary search algorithm. The optimization is relatively noticeable when the number of elements to sort is large.

Time complexity

Binary insertion sort has the same basic idea as direct insertion sort. It only optimizes the constant in the time complexity of insertion sort, so the optimized time complexity remains unchanged.

Code Implementation

C++

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;
    // Moving elements with memmove is faster than using a for loop; the time complexity remains O(n)
    memmove(arr + index + 1, arr + index, (i - index) * sizeof(int));
    arr[index] = key;
  }
}