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.