Insertion Sort

Insertion sort works the same way most people sort a hand of playing cards: pick the next unsorted card, slide it left past every card that is larger, and drop it into its correct slot. The sorted region grows by one element per pass until the entire hand is ordered.

The Shift-Right Pattern

The key implementation choice is whether to use swaps or shifts. The swap approach exchanges adjacent elements, requiring two assignments per step. The shift approach reads the current element into a temporary variable, then shifts larger elements one slot to the right, and finally writes the temp value into the now-open slot. Shifting does one write per step instead of two, making it roughly twice as fast in practice for random data.

JavaScript Implementation

function insertionSort(arr) {
  const n = arr.length;

  for (let i = 1; i < n; i++) {
    const key = arr[i]; // element to be inserted
    let j = i - 1;

    // Shift elements greater than key one position to the right
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }

    // Drop key into the vacated slot
    arr[j + 1] = key;
  }

  return arr;
}

console.log(insertionSort([4, 3, 2, 10, 12, 1, 5, 6]));
// => [1, 2, 3, 4, 5, 6, 10, 12]

Adaptive Behaviour

The inner while loop exits as soon as it finds an element no larger than key. On an already-sorted array, the condition arr[j] > key is never true, so the inner loop runs 0 iterations per outer step — giving O(n) total work. On a nearly-sorted array (each element at most k positions from its sorted slot), the total work is O(kn), which is nearly linear for small k.

This adaptive property is why insertion sort is preferred for small sub-arrays in practice. TimSort, the algorithm used by V8’s Array.prototype.sort, uses insertion sort for runs shorter than about 64 elements.

Stability

Equal elements are never moved past each other because the shift condition is strictly greater (arr[j] > key). Elements equal to key stop the inner loop immediately, leaving the original relative order intact. Insertion sort is stable.

Complexity

The worst case occurs when the input is sorted in reverse order — every element must be shifted all the way to position 0.

When to Use It

Use insertion sort when the array has fewer than roughly 20 elements or is known to be nearly sorted. For larger arbitrary data, merge sort or quicksort will dominate. In library implementations, insertion sort is almost always used as the small-array subroutine inside a faster divide-and-conquer algorithm.

Up Next

Merge sort is the first algorithm that achieves the optimal O(n log n) in all cases, using a divide-and-conquer strategy to break the problem into smaller pieces.