Algorithms · Sorting

Insertion Sort

The idea

You are holding cards. The cards in your left hand are already in order. You pick up the next card from the table and walk it left, one neighbour at a time, until the card on its left is smaller. Slot it in. Repeat until the table is empty.

The problem

Sort the way most people sort playing cards: keep the left part of your hand sorted, pick up the next card, and slide it left past every bigger card until it sits in its right spot.

Why it's slow

On a shuffled list insertion sort is O(n²): a card may walk all the way left, costing up to n(n-1)/2 comparisons and swaps (6 and 6 for our reversed 4-item example). But here is its superpower: on an ALREADY sorted list every card needs exactly one comparison and zero swaps — O(n). Nearly-sorted data is its home turf, which is why real-world libraries still use it for small or almost-ordered chunks.

Pseudocode

  1. pick up the next card (position i)
    Explain this line

    i moves right; everything to its left is always already sorted.

  2. while there is a bigger card on its left
    Explain this line

    The walk stops the moment the left neighbour is not bigger.

  3. compare the pair
    Explain this line

    On nearly-sorted lists most cards need just this ONE comparison.

  4. swap the card one step left
    Explain this line

    The picked-up card slides left one slot per swap.

  5. everything up to i is now in order
    Explain this line

    The sorted zone grows by one card each round.

Complexity

Best Average Worst Space
O(n) O(n²) O(n²) O(1)

The comeback kid: quadratic in general, but linear on sorted or nearly-sorted input — a best case bubble and selection sort can only dream of.

Code

python 
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]
            j -= 1
        a[j + 1] = key
    return a
java 
void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}
cpp 
void insertionSort(std::vector<int>& a) {
    for (size_t i = 1; i < a.size(); ++i) {
        int key = a[i];
        int j = static_cast<int>(i) - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            --j;
        }
        a[j + 1] = key;
    }
}
javascript 
function insertionSort(a) {
  for (let i = 1; i < a.length; i++) {
    const key = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
  return a;
}
dart 
void insertionSort(List<int> a) {
  for (var i = 1; i < a.length; i++) {
    final key = a[i];
    var j = i - 1;
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
}

Quick check