Insertion Sort Algorithm in DSA Javascript

Mental Model

Insertion sort builds a sorted list one item at a time by placing each new item into its correct position.

Analogy: Imagine sorting playing cards in your hand by picking one card at a time and inserting it into the right spot among the cards you already sorted.

Unsorted array:
[5, 3, 8, 4, 2]

Sorted portion ↑
[5, 3, 8, 4, 2]
 ↑

Dry Run Walkthrough

Input: array: [5, 3, 8, 4, 2]

Goal: Sort the array in ascending order using insertion sort

Step 1: Take element 3 and compare with 5, shift 5 right

[5, 5, 8, 4, 2] ↑ (insertion point found)

Why: We move 5 to the right to make space for 3 in the sorted part

Step 2: Insert 3 at position 0

[3, 5, 8, 4, 2] ↑

Why: 3 is smaller than 5, so it goes before 5

Step 3: Take element 8, no shift needed as 8 > 5

[3, 5, 8, 4, 2] ↑

Why: 8 is already in correct position

Step 4: Take element 4, shift 8 and 5 right to insert 4

[3, 5, 8, 8, 2] ↑

Why: We move 8 right to make space for 4

Step 5: Shift 5 right to continue making space for 4

[3, 5, 5, 8, 2] ↑

Why: 5 is greater than 4, so it moves right

Step 6: Insert 4 at position 1

[3, 4, 5, 8, 2] ↑

Why: 4 fits between 3 and 5

Step 7: Take element 2, shift 8, 5, 4, 3 right to insert 2

[3, 4, 5, 8, 8] ↑

Why: Shift 8 right to make space for 2

Step 8: Shift 5 right

[3, 4, 5, 5, 8] ↑

Why: Shift 5 right to continue making space

Step 9: Shift 4 right

[3, 4, 4, 5, 8] ↑

Why: Shift 4 right to continue making space

Step 10: Shift 3 right

[3, 3, 4, 5, 8] ↑

Why: Shift 3 right to continue making space

Step 11: Insert 2 at position 0

[2, 3, 4, 5, 8] ↑

Why: 2 is smallest, goes at start

Result:

[2, 3, 4, 5, 8]

Annotated Code

DSA Javascript

class InsertionSort {
  static sort(arr) {
    for (let i = 1; i < arr.length; i++) {
      let key = arr[i];
      let j = i - 1;
      // Move elements greater than key one position ahead
      while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
      }
      arr[j + 1] = key;
    }
    return arr;
  }
}

// Driver code
const array = [5, 3, 8, 4, 2];
const sortedArray = InsertionSort.sort(array);
console.log(sortedArray.join(", ") + "\n");

for (let i = 1; i < arr.length; i++) {

iterate over each element starting from second to insert it correctly

let key = arr[i];

store current element to insert

while (j >= 0 && arr[j] > key) {

shift elements greater than key to the right

arr[j + 1] = arr[j];

move element one position right to make space

j--;

move left to compare next element

arr[j + 1] = key;

insert key at correct sorted position

Output

2, 3, 4, 5, 8

Complexity Analysis

Time: O(n^2) because in worst case each element is compared and shifted with all previous elements

Space: O(1) because sorting is done in place without extra storage

vs Alternative: Compared to bubble sort, insertion sort is often faster on nearly sorted data because it stops shifting early

Edge Cases

empty array

returns empty array immediately without errors

DSA Javascript

for (let i = 1; i < arr.length; i++) {

array with one element

returns the same single-element array as sorted

DSA Javascript

for (let i = 1; i < arr.length; i++) {

array with all elements equal

no shifts occur, returns the same array

DSA Javascript

while (j >= 0 && arr[j] > key) {

When to Use This Pattern

When you need to sort a small or nearly sorted list by inserting elements one by one, reach for insertion sort because it builds the sorted list gradually and efficiently.

Common Mistakes

Mistake: Not shifting elements to the right before inserting the key, causing overwriting values
Fix: Use a while loop to shift all elements greater than key one position right before inserting key

Mistake: Starting the outer loop from index 0 instead of 1
Fix: Start from index 1 because the first element is trivially sorted

Summary

Insertion sort builds a sorted array by inserting each element into its correct position.

Use it for small or nearly sorted arrays where simple insertion is efficient.

The key insight is shifting larger elements right to make space for the current element.

Practice

1. What is the main idea behind the Insertion Sort algorithm?

easy

A. Build the sorted array one element at a time by inserting elements in the correct position

B. Divide the array into halves and sort each half separately

C. Swap adjacent elements if they are in the wrong order repeatedly

D. Select the smallest element and swap it with the first unsorted element

Solution

1. Step 1: Understand insertion sort process

   Insertion sort builds the sorted list by taking one element at a time and placing it in the correct position among the already sorted elements.

2. Step 2: Compare with other sorting methods

   Other options describe different algorithms: dividing (merge sort), swapping adjacent (bubble sort), selecting smallest (selection sort).

3. Final Answer:

   Build the sorted array one element at a time by inserting elements in the correct position -> Option A

4. Quick Check:

   Insertion sort = Insert elements step-by-step [OK]

Hint: Insertion sort inserts elements one by one in order [OK]

Common Mistakes:

• Confusing insertion sort with bubble sort
• Thinking it divides the array like merge sort
• Mixing it up with selection sort

2. Which of the following is the correct syntax to start the outer loop for insertion sort in JavaScript for an array arr?

easy

A. for(let i = 0; i < arr.length; i++)

B. for(let i = 1; i < arr.length; i++)

C. for(let i = arr.length - 1; i >= 0; i--)

D. for(let i = 0; i <= arr.length; i++)

Solution

1. Step 1: Identify starting index for insertion sort

   Insertion sort starts from the second element (index 1) because the first element is considered sorted.

2. Step 2: Check loop condition correctness

   The loop runs while i < arr.length to cover all elements. Starting at 0 or going beyond length is incorrect.

3. Final Answer:

   for(let i = 1; i < arr.length; i++) -> Option B

4. Quick Check:

   Start loop at 1 for insertion sort [OK]

Hint: Start outer loop at 1, not 0, in insertion sort [OK]

Common Mistakes:

• Starting loop at 0 instead of 1
• Using <= instead of < in loop condition
• Looping backwards incorrectly

3. What will be the output of the following JavaScript code?

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([4, 2, 7, 1]));

medium

A. [2, 1, 4, 7]

B. [4, 2, 7, 1]

C. [1, 4, 2, 7]

D. [1, 2, 4, 7]

Solution

1. Step 1: Trace first iteration (i=1)

   key=2, compare with 4, shift 4 right, insert 2 at index 0 -> [2,4,7,1]

2. Step 2: Trace remaining iterations

   i=2: key=7, no shift -> [2,4,7,1]; i=3: key=1, shift 7,4,2 right, insert 1 at index 0 -> [1,2,4,7]

3. Final Answer:

   [1, 2, 4, 7] -> Option D

4. Quick Check:

   Sorted array = [1, 2, 4, 7] [OK]

Hint: Insertion sort outputs sorted array in ascending order [OK]

Common Mistakes:

• Not shifting elements correctly
• Returning original array without sorting
• Confusing key placement index

4. Find the error in this insertion sort code snippet:

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;
}

medium

A. The outer loop condition should be i < arr.length instead of <=.

B. The inner while loop condition should be arr[j] < key.

C. The key should be assigned after the while loop, not before.

D. The variable j should start at i, not i - 1.

Solution

1. Step 1: Check outer loop boundary

   The loop runs from 1 to arr.length inclusive, but array indices go from 0 to arr.length - 1, so i < arr.length is correct.

2. Step 2: Verify other parts

   Inner loop condition and key assignment are correct; j starts at i - 1 to compare with previous elements.

3. Final Answer:

   The outer loop condition should be i < arr.length instead of <=. -> Option A

4. Quick Check:

   Loop must not exceed array length [OK]

Hint: Use i < arr.length to avoid out-of-bounds [OK]

Common Mistakes:

• Using <= causes index out of range error
• Changing inner loop condition incorrectly
• Misplacing key assignment

5. Given the array [3, 0, -2, 5, 1], after the second iteration (i=2) of insertion sort, what will the array look like?

hard

A. [0, 3, -2, 5, 1]

B. [0, -2, 3, 5, 1]

C. [-2, 0, 3, 5, 1]

D. [3, 0, -2, 5, 1]

Solution

1. Step 1: Trace first iteration (i=1)

   key=0, compare with 3, shift 3 right, insert 0 at index 0 -> [0,3,-2,5,1]

2. Step 2: Trace second iteration (i=2)

   key=-2, compare with 3 and 0, shift both right, insert -2 at index 0 -> [-2,0,3,5,1]

3. Final Answer:

   [-2, 0, 3, 5, 1] -> Option C

4. Quick Check:

   After 2 iterations, array is partially sorted [OK]

Hint: After i-th iteration, first i+1 elements are sorted [OK]

Common Mistakes:

• Not shifting all larger elements
• Inserting key at wrong position
• Confusing iteration count with index