Insertion Sort Algorithm in DSA Go - Execution Trace

Concept Flow - Insertion Sort Algorithm

Start with second element i=1

↓

Compare current element with elements before it

↓

Shift elements greater than current to the right

↓

Insert current element at correct position

↓

Increment i and repeat until end of array

↓

Done

Insertion sort takes each element from the second position and inserts it into the sorted part on the left by shifting larger elements right.

Execution Sample

DSA Go

arr := []int{5, 3, 8, 1, 2}
for i := 1; i < len(arr); i++ {
  key := arr[i]
  j := i - 1
  for j >= 0 && arr[j] > key {
    arr[j+1] = arr[j]
    j--
  }
  arr[j+1] = key
}

This code sorts the array by inserting each element into its correct place among the previously sorted elements.

Execution Table

Step	Operation	Array State	Comparison	Swap/Shift	Resulting Array
1	Pick key=3 at index 1	[5, 3, 8, 1, 2]	5 > 3	Shift 5 right	[5, 5, 8, 1, 2]
2	Insert key=3 at index 0	[5, 5, 8, 1, 2]	N/A	Insert 3	[3, 5, 8, 1, 2]
3	Pick key=8 at index 2	[3, 5, 8, 1, 2]	5 > 8? No	No shift	[3, 5, 8, 1, 2]
4	Pick key=1 at index 3	[3, 5, 8, 1, 2]	8 > 1	Shift 8 right	[3, 5, 8, 8, 2]
5	Compare 5 > 1	[3, 5, 8, 8, 2]	5 > 1	Shift 5 right	[3, 5, 5, 8, 2]
6	Compare 3 > 1	[3, 5, 5, 8, 2]	3 > 1	Shift 3 right	[3, 3, 5, 8, 2]
7	Insert key=1 at index 0	[3, 3, 5, 8, 2]	N/A	Insert 1	[1, 3, 5, 8, 2]
8	Pick key=2 at index 4	[1, 3, 5, 8, 2]	8 > 2	Shift 8 right	[1, 3, 5, 8, 8]
9	Compare 5 > 2	[1, 3, 5, 8, 8]	5 > 2	Shift 5 right	[1, 3, 5, 5, 8]
10	Compare 3 > 2	[1, 3, 5, 5, 8]	3 > 2	Shift 3 right	[1, 3, 3, 5, 8]
11	Compare 1 > 2	[1, 3, 3, 5, 8]	1 > 2? No	No shift	[1, 3, 3, 5, 8]
12	Insert key=2 at index 1	[1, 3, 3, 5, 8]	N/A	Insert 2	[1, 2, 3, 5, 8]
13	End of array reached	[1, 2, 3, 5, 8]	N/A	N/A	[1, 2, 3, 5, 8]

💡 i reaches length of array, sorting complete

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 7	After Step 12	Final
i	1	2	3	4	5	5
key	3	8	1	2	N/A	N/A
j	0	1	2	3	N/A	N/A
arr	[5,3,8,1,2]	[3,5,8,1,2]	[3,5,8,1,2]	[1,3,5,8,2]	[1,2,3,5,8]	[1,2,3,5,8]

Key Moments - 3 Insights

Why do we shift elements instead of swapping them directly?

In the execution_table rows 1,4,5,6,8,9,10, shifting moves larger elements right to make space for the key, avoiding multiple swaps and preserving order.

Why does the inner loop stop when arr[j] <= key?

As seen in steps 3 and 11, when arr[j] is not greater than key, the correct position is found, so no more shifting is needed.

What happens when the key is already greater than all sorted elements?

In step 3, key=8 is greater than 5, so no shifts occur and key stays in place, showing insertion sort skips unnecessary moves.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the array state after shifting?

A [5, 5, 8, 1, 2]

B [3, 3, 5, 8, 2]

C [3, 5, 5, 8, 2]

D [3, 5, 8, 8, 2]

💡 Hint

Check the 'Resulting Array' column at step 5 in execution_table

At which step does the key=1 get inserted into the array?

A Step 6

B Step 7

C Step 4

D Step 3

💡 Hint

Look for 'Insert key=1' operation in execution_table

If the initial array was already sorted, how would the execution_table change?

A No shifts would occur, only comparisons

B The key would always be inserted at index 0

C Many shifts would occur

D The array would be reversed

💡 Hint

Refer to steps where no shifts happen, like step 3 and 11

Concept Snapshot

Insertion Sort Algorithm:
- Start from second element
- Compare with sorted left side
- Shift larger elements right
- Insert key at correct spot
- Repeat until array sorted
- Efficient for small or nearly sorted arrays

Full Transcript

Insertion sort works by taking each element from the second position and inserting it into the correct place among the elements before it. It compares the key element with elements to its left, shifting larger elements one position to the right to make space. When the correct position is found, the key is inserted. This repeats until the entire array is sorted. The execution table shows each step with array states, comparisons, shifts, and insertions. Key moments clarify why shifting is used instead of swapping, when the inner loop stops, and what happens if the key is already in the right place. The visual quiz tests understanding of array states after shifts, insertion steps, and behavior on sorted arrays.