Insertion Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Insertion Sort

Take each new element and slide it left over larger neighbors until it lands in the right slot — like sorting a hand of cards.

How it works

Insertion Sort grows a sorted prefix one element at a time. For each new element, it shifts larger neighbors right by one position to open a slot, then drops the element in.

1. The first element forms a trivially-sorted prefix of length 1.
2. Pick the next element as the key.
3. Compare against elements in the sorted prefix from right to left, shifting any that are greater than the key.
4. Insert the key in the resulting gap.

The shift is what makes Insertion Sort stable and adaptive: on a nearly-sorted array it runs in close to linear time because almost no shifts are needed.

Complexity

Interactive visualization

Pseudocode

procedure insertionSort(A):
  for i from 1 to n − 1:
    key ← A[i]
    j ← i − 1
    while j ≥ 0 and A[j] > key:
      A[j+1] ← A[j]
      j ← j − 1
    A[j+1] ← key

JavaScript implementation

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

Pros and cons

When to use it

• Base case in hybrid sorts (TimSort, IntroSort).
• Almost-sorted streams where best-case linearity wins.
• Tiny arrays in any setting.