Insertion Sort

Category: Classical
Difficulty: Beginner
Time Complexity: O(n²)
Space Complexity: O(1)

Overview

Insertion Sort grows a sorted region at the front of the array. For each new element, it walks leftward through the already-sorted region, swapping the element with its neighbour until it reaches its correct position. It is stable, in-place, and O(n²) in the worst case, but O(n) on nearly-sorted input — which makes it excellent for small or almost-sorted arrays. It is also the algorithm most people use instinctively when sorting a hand of playing cards.

Try It

• Web: Open in Eigenvue →
• Python:

  import eigenvue
  eigenvue.show("insertion-sort")

Default Inputs

{
  "array": [
    5,
    2,
    8,
    1,
    9,
    3
  ]
}

Input Examples

Default

{
  "array": [
    5,
    2,
    8,
    1,
    9,
    3
  ]
}

Already sorted (best case)

{
  "array": [
    1,
    2,
    3,
    4,
    5
  ]
}

Reverse sorted (worst case)

{
  "array": [
    5,
    4,
    3,
    2,
    1
  ]
}

With duplicates

{
  "array": [
    3,
    1,
    3,
    2,
    1
  ]
}

Single element

{
  "array": [
    42
  ]
}

Code

Pseudocode

function insertionSort(array):
  for i = 1 to length(array) - 1:
    j = i
    while j > 0 and array[j - 1] > array[j]:
      swap(array[j - 1], array[j])
      j = j - 1
  return array

Python

def insertion_sort(array: list[int]) -> list[int]:
    for i in range(1, len(array)):
        key = array[i]
        j = i - 1
        while j >= 0 and array[j] > key:
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = key
    return array

JavaScript

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    const key = array[i];
    let j = i - 1;
    while (j >= 0 && array[j] > key) {
      array[j + 1] = array[j];
      j--;
    }
    array[j + 1] = key;
  }
  return array;
}

Key Concepts

Growing a Sorted Region

At the start of iteration i, the sub-array array[0..i-1] is already sorted. Insertion Sort places array[i] into that region so that array[0..i] becomes sorted. The invariant holds until the whole array is sorted.

Stability

Insertion Sort is stable: it only swaps when the left element is strictly greater than the right, so equal elements never cross each other and keep their original relative order.

Adaptive Performance

On a nearly-sorted array, most elements are already in place, so the inner loop rarely runs. This gives O(n) best-case time — one of the reasons Insertion Sort is used as the base case inside faster hybrid sorts like Timsort.

Common Pitfalls

• Confusing it with Selection Sort: Insertion Sort inserts the next element into the sorted region; Selection Sort repeatedly selects the minimum of the unsorted region. Insertion Sort is adaptive and stable; Selection Sort is neither.
• Off-by-one in the inner loop: The inner loop must stop at j = 0. Comparing array[j - 1] when j = 0 reads out of bounds. The condition j > 0 guards against this.

Quiz

Q1: What is the best-case time complexity of Insertion Sort?

• A) O(1)
• B) O(n)
• C) O(n log n)
• D) O(n²)

Show answer

Answer: B) O(n)

On an already-sorted array the inner loop never swaps, so the algorithm makes a single pass of n - 1 comparisons — O(n).

Q2: Is Insertion Sort stable?

• A) Yes
• B) No
• C) Only for integers
• D) Only when reversed

Show answer

Answer: A) Yes

It swaps only on a strict greater-than comparison, so equal elements never change their relative order — making it stable.

Q3: Which scenario is Insertion Sort especially good at?

• A) Large random arrays
• B) Nearly-sorted arrays
• C) Reverse-sorted arrays
• D) Arrays with all equal elements only

Show answer

Answer: B) Nearly-sorted arrays

On nearly-sorted input most elements are already in place, so the inner loop does little work, giving near-linear performance.

Further Reading

• Insertion Sort — Wikipedia (reference)

Related Algorithms

• Bubble Sort
• Selection Sort
• Merge Sort