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 TypeScript 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.ts
Replay: real traced execution (multi-file project)
const arr: number[] = [5, 1, 4, 2, 8];
for (let i: number = 1; i < arr.length; i++) {
    const key: number = arr[i];
    let j: number = 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: number[] = [5, 1, 4, 2, 8];2for (let i: number = 1; i < arr.length; i++) {
    values this step[5, 1, 4, 2, 8]arr

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

    2for (let i: number = 1; i < arr.length; i++) {3    const key: number = arr[i];4    let j: number = 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: number = 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: number = 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: number[] = [5, 1, 4, 2, 8];2for (let i: number = 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

  • TypeScript declares the sortable data as const arr: number[]. The binding is constant, but the array slots are mutated in place.
  • Each outer pass uses typed numeric indices, let i: number and let j: number, and copies the current value into const key: number.
  • The while (j >= 0 && arr[j] > key) guard keeps indexed reads in range and compares JavaScript Number values through TypeScript's number type.
  • Shifts are direct writes: arr[j + 1] = arr[j] moves a larger value right, then arr[j + 1] = key places the saved value. The input array is not replaced.
  • The replay shows 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)) prints [1,2,4,5,8]; visible allocation is the initial array and output string.