Insertion Sort Algorithm in DSA Javascript - Execution Trace

Concept Flow - Insertion Sort Algorithm

Start at index 1

↓

Pick key element

↓

Compare with elements to left

↓

Shift elements right if greater

↓

Insert key at correct position

↓

Move to next index

↓

Repeat until end of array

↓

Sorted array

Insertion sort picks each element from the unsorted part and inserts it into the correct position in the sorted part by shifting larger elements to the right.

Execution Sample

DSA Javascript

const arr = [5, 3, 8, 1];
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;
}

Sorts the array [5, 3, 8, 1] step-by-step by inserting each element into its correct position.

Execution Table

Step	Operation	Index i	Key	Index j	Comparison	Shift or Insert	Array State
1	Start outer loop	1	3	0	arr[0]=5 > 3	Shift arr[0] to arr[1]	[5, 5, 8, 1]
2	Continue inner loop	1	3	-1	j < 0, stop	Insert key at arr[0]	[3, 5, 8, 1]
3	Start outer loop	2	8	1	arr[1]=5 > 8? No	Insert key at arr[2]	[3, 5, 8, 1]
4	Start outer loop	3	1	2	arr[2]=8 > 1	Shift arr[2] to arr[3]	[3, 5, 8, 8]
5	Continue inner loop	3	1	1	arr[1]=5 > 1	Shift arr[1] to arr[2]	[3, 5, 5, 8]
6	Continue inner loop	3	1	0	arr[0]=3 > 1	Shift arr[0] to arr[1]	[3, 3, 5, 8]
7	Continue inner loop	3	1	-1	j < 0, stop	Insert key at arr[0]	[1, 3, 5, 8]
8	Outer loop ends	4	-	-	-	-	[1, 3, 5, 8]

💡 Outer loop index i reaches array length 4, sorting complete.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
i	undefined	1	1	2	3	3	3	3	4
key	undefined	3	3	8	1	1	1	1	-
j	undefined	0	-1	1	2	1	0	-1	-
arr	[5, 3, 8, 1]	[5, 5, 8, 1]	[3, 5, 8, 1]	[3, 5, 8, 1]	[3, 5, 8, 8]	[3, 5, 5, 8]	[3, 3, 5, 8]	[1, 3, 5, 8]	[1, 3, 5, 8]

Key Moments - 3 Insights

Why do we shift elements to the right instead of swapping directly?

We shift elements to the right to make space for the key element. Swapping repeatedly would be less efficient. See steps 1, 4-6 in execution_table where shifting happens before inserting the key.

Why does the inner loop stop when j becomes -1?

j becomes -1 when we have compared the key with all elements to the left and found no smaller element. This means the key belongs at the start. See steps 2 and 7 where j < 0 stops the loop.

Why do we insert the key at arr[j+1] after shifting?

After shifting larger elements right, j points to one position left of where the key should go. So we insert at j+1. This is shown in steps 2, 3, and 7.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What happens to the array?

A Element 5 is shifted right to index 3

B The key 1 is inserted at index 3 without shifts

C Element 8 at index 2 is shifted right to index 3

D No changes to the array

💡 Hint

Check the 'Shift or Insert' and 'Array State' columns at step 4.

At which step does the inner loop stop because j < 0?

A Step 1

B Step 2

C Step 3

D Step 5

💡 Hint

Look for 'j < 0, stop' in the 'Comparison' column.

If the initial array was already sorted, how would the 'Shift or Insert' column change?

A There would be no shifts, only inserts at the same position

B All elements would be shifted right

C The key would always be inserted at index 0

D The array would be reversed

💡 Hint

Consider how insertion sort behaves when elements are already in order.

Concept Snapshot

Insertion Sort Algorithm:
- Start from index 1, pick key element
- Compare key with sorted part to left
- Shift larger elements right
- Insert key at correct position
- Repeat until array end
- Time: O(n^2), best O(n) if sorted

Full Transcript

Insertion sort works by taking one element at a time from the unsorted part of the array and inserting it into the correct position in the sorted part. We start from the second element (index 1) and pick it as the key. We compare the key with elements to its left. If elements are larger, we shift them right to make space. When we find the correct spot or reach the start, we insert the key. This repeats until the whole array is sorted. The execution table shows each step, including comparisons, shifts, and insertions, with the array state after each operation. Key variables tracked are i (outer loop index), j (inner loop index), key (current element), and the array itself. Important points include why shifting is used instead of swapping, why the inner loop stops when j < 0, and why insertion happens at arr[j+1]. The quiz questions test understanding of these steps and the behavior of insertion sort on sorted arrays.

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