Sorting

Insertion Sort

Build the sorted prefix one item at a time, shifting larger values right until the current key can be inserted.

Algorithm

The checked-in replay follows the same small input and final output across all 21 DSA books, so this JavaScript DSA implementation can be compared directly with the other languages.

Basic Implementation

basic.js 
const arr = [5, 1, 4, 2, 8];
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;
}
console.log(JSON.stringify(arr));

Complexity

  • Time: O(n^2) worst and average, O(n) best
  • Space: O(1)
  • Stable: yes

Implementation notes

  • JavaScript stores the sortable data in a const Array of Number values. The binding is constant, but the array slots are mutated in place; no replacement array or built-in sort is used.
  • Each outer-loop pass copies arr[i] into const key and tracks the sorted prefix with let j = i - 1. The while (j >= 0 && arr[j] > key) guard keeps indexed reads in range and uses numeric Number comparison.
  • Shifts are direct slot writes: arr[j + 1] = arr[j] moves a larger value right, then arr[j + 1] = key places the saved value. Using strict > means equal values would keep their original relative order.
  • The replay-visible mutations are insert 1 before 5, shift 5 and insert 4, and shift 5 and 4, insert 2, ending with [1, 2, 4, 5, 8]. console.log(JSON.stringify(arr)) creates the compact output string [1,2,4,5,8]; aside from that string and the initial array, the sort creates no ongoing JavaScript GC pressure.
sorted prefix Positions before the scan index are already sorted.
shifting Larger values move one slot right to make room for the key.