Insertion Sort

Insertion Sort

Insertion sort works exactly like how you sort playing cards in your hand. You pick up one card at a time and slide it into its correct position among the cards you've already sorted. Simple, intuitive, and surprisingly effective for certain situations.

The algorithm builds the sorted array one element at a time. For each element, it shifts larger elements to the right to make room. This "shifting" is what makes it efficient for nearly sorted data — if most elements are already in place, you do very little work.

Step-by-Step Visualization

Let's sort [5, 2, 4, 6, 1, 3]. Start with [5]. Insert 2 before 5 → [2, 5]. Insert 4 between 2 and 5 → [2, 4, 5]. Insert 6 after 5 → [2, 4, 5, 6]. Insert 1 before everything → [1, 2, 4, 5, 6]. Insert 3 between 2 and 4 → [1, 2, 3, 4, 5, 6].

Notice how each step only shifts the elements that need to move. If the new element is already bigger than everything before it, no shifting happens at all. That's why insertion sort shines on nearly sorted data.

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let 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([5, 2, 4, 6, 1, 3]));

Time Complexity

Worst case is O(n²) — when the array is in reverse order, every element has to shift past all previous elements. Best case is O(n) — when the array is already sorted, the inner loop never executes. Average case is still O(n²), but with a small constant factor.

Space complexity is O(1) — it sorts in place. The combination of O(1) space and O(n) best case makes insertion sort the go-to choice for small or nearly sorted datasets.

Best for Small or Nearly Sorted Data

Here's a pro tip: many optimized sorting libraries use insertion sort as a base case. When merge sort or quick sort breaks the problem into small subarrays (say, 16-32 elements), they switch to insertion sort because it's faster for small n. The overhead of recursion isn't worth it for tiny chunks.

Insertion sort is also adaptive — it naturally takes advantage of existing order in the data. If you're maintaining a sorted list and adding elements one at a time, insertion sort is your best friend. It's also stable, which is a nice bonus.