Insertion Sort Explained: Algorithm, Code & Complexity

Insertion sort builds the final sorted array one element at a time, the way you sort a hand of playing cards: pick up the next card and slide it left until it sits in the right spot among the cards you already arranged. It is the best of the simple O(n²) sorts — fast on small or nearly-sorted inputs, stable, and in-place — which is why real libraries fall back to it for tiny subarrays.

The idea

Treat the first element as a sorted prefix of length 1. For each following element key, shift every larger element in the prefix one slot to the right, then drop key into the gap. The prefix stays sorted and grows by one each step.

Tracing [5, 2, 4] ascending: take 2, shift 5 right, insert 2 → [2, 5, 4]; take 4, shift 5 right, insert 4 → [2, 4, 5].

Implementation

void insertionSort(std::vector<int>& a) {
    int n = (int)a.size();
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j]; // shift right
            j--;
        }
        a[j + 1] = key;      // drop key into the gap
    }
}

void insertionSort(int[] a) {
    int n = a.length;
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j]; // shift right
            j--;
        }
        a[j + 1] = key;      // drop key into the gap
    }
}

function insertionSort(a) {
  const n = a.length;
  for (let i = 1; i < n; i++) {
    const key = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j]; // shift right
      j--;
    }
    a[j + 1] = key;    // drop key into the gap
  }
}

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]  # shift right
            j -= 1
        a[j + 1] = key       # drop key into the gap

Complexity

• Space: O(1) — in-place.
• Stable: yes — the test is strict > , so an equal element stops the shift and keeps its original order.
• Online: it can sort a stream, inserting each new element as it arrives.

For beginners: Note the > (not >=) in the while condition. Using >= would shift equal elements too, breaking stability and doing useless work.

When to use it

• Small arrays (roughly n ≤ 16). It beats O(n log n) sorts here because it has tiny constants and no recursion overhead — this is exactly why quick sort and merge sort implementations switch to insertion sort for small subarrays.
• Nearly-sorted data, where its O(n) best case shines.

For large, random data, prefer an O(n log n) sort — see the comparison page and the built-in sorts.

Next: Merge Sort.