JavaScript Program for Insertion Sort Algorithm

Use the function insertionSort(arr) that loops through the array and inserts each element into its correct position by shifting larger elements to the right.

Examples

Input[5, 2, 9, 1]

Output[1, 2, 5, 9]

Input[3, 3, 2, 1]

Output[1, 2, 3, 3]

Input[]

Output[]

How to Think About It

Think of sorting like organizing playing cards in your hand. You pick one card at a time and place it in the right spot among the cards you already sorted. You compare the new card with the sorted cards and shift them if needed to make space.

Algorithm

1

Start from the second element in the array.

2

Compare it with elements before it.

3

Shift all larger elements one position to the right.

4

Insert the current element into the correct position.

5

Repeat for all elements until the array is sorted.

Code

javascript

function insertionSort(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(insertionSort([5, 2, 9, 1]));

Output

[1, 2, 5, 9]

Dry Run

Let's trace [5, 2, 9, 1] through the code

1

Start with second element

key = 2, compare with 5, shift 5 right, insert 2 before 5 -> [2, 5, 9, 1]

2

Next element

key = 9, compare with 5, no shift needed, array stays [2, 5, 9, 1]

3

Last element

key = 1, compare with 9, 5, 2, shift all right, insert 1 at start -> [1, 2, 5, 9]

Iteration	Array State
i=1	[2, 5, 9, 1]
i=2	[2, 5, 9, 1]
i=3	[1, 2, 5, 9]

Why This Works

Step 1: Pick element to insert

The code picks the element at index i as key to place it correctly.

Step 2: Shift larger elements

It moves all elements larger than key one step right to make space.

Step 3: Insert key

Finally, it inserts key into the correct position, keeping the left side sorted.

Alternative Approaches

Using recursion

javascript

function insertionSortRecursive(arr, n = arr.length) {
  if (n <= 1) return arr;
  insertionSortRecursive(arr, n - 1);
  let last = arr[n - 1];
  let j = n - 2;
  while (j >= 0 && arr[j] > last) {
    arr[j + 1] = arr[j];
    j--;
  }
  arr[j + 1] = last;
  return arr;
}

console.log(insertionSortRecursive([5, 2, 9, 1]));

Recursion can be elegant but uses more memory and is less common for insertion sort.

Using built-in sort with custom comparator

javascript

function insertionSortWithBuiltIn(arr) {
  return arr.sort((a, b) => a - b);
}

console.log(insertionSortWithBuiltIn([5, 2, 9, 1]));

This is simpler but does not demonstrate the insertion sort algorithm itself.

Complexity: O(n²) time, O(1) space

Time Complexity

Insertion sort uses nested loops: the outer loop runs n times, and the inner loop can run up to n times in the worst case, making it O(n²).

Space Complexity

It sorts the array in place without extra arrays, so space complexity is O(1).

Which Approach is Fastest?

Built-in sort is fastest for large arrays, but insertion sort is simple and efficient for small or nearly sorted arrays.

Approach	Time	Space	Best For
Insertion Sort	O(n²)	O(1)	Small or nearly sorted arrays
Recursive Insertion Sort	O(n²)	O(n) due to recursion stack	Learning recursion
Built-in Sort	O(n log n)	O(n) or O(1) depending on engine	General purpose sorting