DEV Community

Cover image for Insertion Sort in JavaScript
Alok Kumar
Alok Kumar

Posted on

Insertion Sort in JavaScript

#algorithms #tutorial #interview #javascript

Insertion Sort is an intuitive, stable, in-place sorting algorithm that builds the final sorted array one item at a time. It’s efficient on small or nearly-sorted arrays and is a common interview staple. This post shows the canonical shift implementation, the descending version, a detailed dry run, and complexity notes.

What Insertion Sort does (plain English)

  • Treat the left portion of the array as sorted (initially the first element).
  • Take the next element (the key) and insert it into the correct position within the sorted portion by shifting larger elements to the right.
  • Repeat until the entire array is sorted.

Think of sorting playing cards in your hand: take the next card and slide it into the right spot.

Canonical (shift-based) Insertion Sort — JavaScript 

const insertion = (arr) => {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;

    // shift elements of arr[0..i-1] that are greater than key
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }

    // place key after the element just smaller than it
    arr[j + 1] = key;
  }

  return arr;
};

console.log(insertion([12, 45, 2, 1, 54, 3]));
// => [1, 2, 3, 12, 45, 54]
Enter fullscreen mode Exit fullscreen mode

Step-by-step Dry Run

Array:

[12, 45, 2, 1, 54, 3]
Enter fullscreen mode Exit fullscreen mode

i = 1 (key = 45)

  • j = 0 → arr[0] (12) > 45? No → insert 45 at index 1
  • Array: [12, 45, 2, 1, 54, 3]

i = 2 (key = 2)

  • j = 1 → 45 > 2 → shift 45 right → [12, 45, 45, 1, 54, 3], j = 0
  • j = 0 → 12 > 2 → shift 12 right → [12, 12, 45, 1, 54, 3], j = -1
  • place key at j+1 = 0 → [2, 12, 45, 1, 54, 3]

i = 3 (key = 1)

  • shift 45, 12, 2 right → place 1 at index 0
  • Array: [1, 2, 12, 45, 54, 3]

i = 4 (key = 54)

  • 45 > 54? No → place 54 at index 4 (no shifts)
  • Array: [1, 2, 12, 45, 54, 3]

i = 5 (key = 3)

  • shift 54, 45, 12 right → place 3 at index 2
  • Final: [1, 2, 3, 12, 45, 54]

Descending Order

To sort descending, flip the comparison (> → <) in the while condition:

const insertionDesc = (arr) => {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] < key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
};

console.log(insertionDesc([12, 45, 2, 1, 54, 3]));
// => [54, 45, 12, 3, 2, 1]
Enter fullscreen mode Exit fullscreen mode

Complexity & Characteristics (Quick Summary)

  • Time Complexity
    • Best: O(n) — when array is already sorted (shift-based; only comparisons)
    • Average: O(n²)
    • Worst: O(n²) — reverse-sorted input
  • Space Complexity: O(1) — in-place
  • Stability: Stable (shift-based sorting preserves equal-element order)
  • When to use: small arrays, nearly-sorted data, or when stability matters
  • Why it’s useful in practice: often used as the base case sorter for hybrid algorithms (Timsort, introsort variants) on small subarrays

Top comments (0)