Skip to content

Insertion Sort

This page provides a brief introduction to insertion sort.

Definition

Insertion sort is a simple and intuitive sorting algorithm. Its working principle is to divide the elements to be sorted into two parts: "sorted" and "unsorted". Each time, it selects one element from the "unsorted" part and inserts it into the correct position within the "sorted" part.

An operation similar to insertion sort is when playing poker: you draw a card from the table, insert it into your hand in order of 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)\), which is highly efficient when the sequence is almost 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} \]
 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 optimized using binary search, which significantly improves performance when sorting a large number of elements.

Time Complexity

The basic idea of binary insertion sort is the same as that of direct insertion sort. Binary insertion sort only optimizes the constant factor in the time complexity of insertion sort, so the optimized time complexity remains unchanged.

Code 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;
    // Using memmove to shift elements is faster than using a for loop, while the time complexity remains O(n)
    memmove(arr + index + 1, arr + index, (i - index) * sizeof(int));
    arr[index] = key;
  }
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用