jsschools

Insertion Sort

Builds a sorted prefix one element at a time by shifting each new element left until it is in the correct position.

Spec ↗

Syntax

insertionSort(arr)

Parameters

NameTypeRequiredDescription
arr Array<number> Yes The mutable array of numbers to sort in-place.

Returns

void — Sorts the input array in-place; returns nothing.

Examples

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;
  }
}

const nums = [12, 11, 13, 5, 6];
insertionSort(nums);
console.log(nums);
Output 
[ 5, 6, 11, 12, 13 ]

// Near-sorted input — very fast in practice
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;
  }
}

const nearly = [1, 2, 4, 3, 5]; // one swap needed
insertionSort(nearly);
console.log(nearly);
Output 
[ 1, 2, 3, 4, 5 ]

Notes

| Case | Time | Space | |---------|--------|-------| | Best | O(n) | O(1) | | Average | O(n²) | O(1) | | Worst | O(n²) | O(1) | Insertion sort is **stable** and adaptive — it degrades gracefully on nearly-sorted data (only O(n) operations). It is the algorithm of choice for small arrays (n ≤ 32) and is used as the base case in Timsort and Introsort. It sorts online: it can process elements one at a time as they arrive.

See also