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.

Practice

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

easy

A. Divide the array into halves and sort each half recursively

B. Build the sorted array one element at a time by inserting elements into their correct position

C. Swap adjacent elements if they are in 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 relative to the already sorted part.

2. Step 2: Compare with other sorting methods

   Other options describe merge sort (B), bubble sort (C), and selection sort (D), which are different algorithms.

3. Final Answer:

   Build the sorted array one element at a time by inserting elements into their correct position -> Option B

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 or selection sort
• Thinking insertion sort divides array recursively
• Assuming insertion sort swaps all elements repeatedly

2. Which of the following Go code snippets correctly starts the outer loop for insertion sort on a slice arr?

easy

A. for i := 1; i < len(arr); i++ {

B. for i := 0; i < len(arr); i++ {

C. for i := len(arr)-1; i >= 0; i-- {

D. for i := 1; i <= len(arr); i++ {

Solution

1. Step 1: Identify correct loop start for insertion sort

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

2. Step 2: Check loop conditions

   Loop runs while i is less than length of array. for i := 1; i < len(arr); i++ { matches this exactly.

3. Final Answer:

   for i := 1; i < len(arr); i++ { -> Option A

4. Quick Check:

   Start from index 1 to end [OK]

Hint: Start outer loop at 1, not 0, for 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 slice after running insertion sort on arr := []int{4, 3, 2, 1}?

medium

A. [1, 3, 2, 4]

B. [4, 3, 2, 1]

C. [1, 2, 3, 4]

D. [2, 3, 4, 1]

Solution

1. Step 1: Trace insertion sort on given array

   Start with 4 (sorted). Insert 3 before 4 -> [3,4,2,1]. Insert 2 before 3 -> [2,3,4,1]. Insert 1 before 2 -> [1,2,3,4].

2. Step 2: Confirm final sorted slice

   The array is sorted in ascending order: [1, 2, 3, 4].

3. Final Answer:

   [1, 2, 3, 4] -> Option C

4. Quick Check:

   Sorted ascending = [1, 2, 3, 4] [OK]

Hint: Insertion sort outputs sorted ascending array [OK]

Common Mistakes:

• Assuming no change in array
• Stopping sorting early
• Mixing up partial sorted states

4. Identify the error in this Go insertion sort snippet:

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] = key
}

medium

A. The outer loop should start from i := 0

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

C. The variable key should be declared outside the loop

D. The final assignment should be arr[j+1] = key, not arr[j] = key

Solution

1. Step 1: Analyze inner loop and final assignment

   After shifting elements greater than key, the correct position is j+1, but code assigns key to arr[j], which is incorrect.

2. Step 2: Correct the assignment

   It should be arr[j+1] = key to place key in the right spot after shifting.

3. Final Answer:

   The final assignment should be arr[j+1] = key, not arr[j] = key -> Option D

4. Quick Check:

   Insert key at arr[j+1] after shifting [OK]

Hint: Assign key to arr[j+1], not arr[j], after shifting [OK]

Common Mistakes:

• Assigning key to wrong index after inner loop
• Reversing comparison operator in inner loop
• Starting outer loop at 0

5. Given a slice arr := []int{5, 2, 9, 1, 5, 6}, how many total element shifts occur during insertion sort?

hard

A. 7

B. 6

C. 8

D. 5

Solution

1. Step 1: Trace shifts for each insertion

   Insert 2: shift 5 -> 1 shift
   Insert 9: no shift -> 0 shifts
   Insert 1: shift 9, 5, 2 -> 3 shifts
   Insert 5: shift 9, 5 -> 2 shifts
   Insert 6: shift 9 -> 1 shift

2. Step 2: Sum all shifts

   Total shifts = 1 + 0 + 3 + 2 + 1 = 7 shifts.

3. Step 3: Verify options

   7 is present as 7.

4. Final Answer:

   7 -> Option A

5. Quick Check:

   Count shifts carefully for each insertion [OK]

Hint: Count shifts by tracing each insertion step [OK]

Common Mistakes:

• Counting comparisons instead of shifts
• Missing shifts when multiple elements move
• Confusing shifts with swaps