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.

sorted prefix Positions before the scan index are already sorted.
shifting Larger values move one slot right to make room for the key.

Basic Implementation

basic.js
Replay: real traced execution (multi-file project)
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));

  1. arr ← [5, 1, 4, 2, 8]

    1const arr = [5, 1, 4, 2, 8];2for (let i = 1; i < arr.length; i++) {
    values this step[5, 1, 4, 2, 8]arr

  2. arr ← [1, 5, 4, 2, 8]

    2for (let i = 1; i < arr.length; i++) {3    const key = arr[i];4    let j = i - 1;
    values this step[5, 1, 4, 2, 8] → [1, 5, 4, 2, 8]arr1key

  3. arr ← [1, 4, 5, 2, 8]

    4let j = i - 1;5while (j >= 0 && arr[j] > key) {6    arr[j + 1] = arr[j];
    values this step[1, 5, 4, 2, 8] → [1, 4, 5, 2, 8]arr4key

  4. arr ← [1, 2, 4, 5, 8]

    4let j = i - 1;5while (j >= 0 && arr[j] > key) {6    arr[j + 1] = arr[j];
    values this step[1, 4, 5, 2, 8] → [1, 2, 4, 5, 8]arr2key

  5. stdout ← [1,2,4,5,8]

    1const arr = [5, 1, 4, 2, 8];2for (let i = 1; i < arr.length; i++) {
    values this step[1,2,4,5,8]stdout[1, 2, 4, 5, 8]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.