Insertion Sort Algorithm

Imagine you're sorting playing cards. You pick up each card and slide it into the right spot among the cards already in your hand. That's insertion sort.

What It Does

Insertion sort builds a sorted portion one element at a time. It takes each element from the unsorted part and inserts it into its correct position in the sorted part, shifting elements as needed.

The Code

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const current = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }

    arr[j + 1] = current;
  }

  return arr;
}

console.log(insertionSort([64, 34, 25, 12, 22, 11, 90]));
// [11, 12, 22, 25, 34, 64, 90]

Step by Step

Array: [64, 34, 25, 12]

1. current = 34. Compare with 64. Shift 64 right. Insert 34. → [34, 64, 25, 12]
2. current = 25. Shift 64, shift 34. Insert 25. → [25, 34, 64, 12]
3. current = 12. Shift 64, 34, 25. Insert 12. → [12, 25, 34, 64]

Complexity

When Insertion Sort Wins

It's O(n²), so it's slow on large arrays. But it has real advantages:

• Nearly sorted data — if the array is almost sorted, insertion sort is nearly O(n). Merge sort is still O(n log n).
• Small arrays — the overhead of recursive algorithms (merge sort, quicksort) makes insertion sort faster for arrays under ~20 elements. Many production sort implementations switch to insertion sort for small subarrays.
• Online sorting — it can sort elements as they arrive, one at a time. You don't need the full array upfront.
• Stable — equal elements keep their original order.

The Trade-off

For large random datasets, insertion sort is too slow. Use merge sort or quicksort. But for small, nearly-sorted, or streaming data, insertion sort is hard to beat.