Insertion Sort Algorithm in DSA Python - 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

↓

Is i < length of array?

No→Done

↩Back to Compare

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 Python

arr = [5, 3, 8, 1, 2]
for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
        arr[j + 1] = arr[j]
        j -= 1
    arr[j + 1] = key

Sorts the array by inserting each element into its correct position in the sorted left side.

Execution Table

Step	Operation	Array State	Comparison	Swap/Shift	Resulting Array
1	Start with i=1, key=3	[5, 3, 8, 1, 2]	Compare 5 > 3	Shift 5 right	[5, 5, 8, 1, 2]
2	j=0 -> j=-1	After shift	No more comparisons	Insert key at j+1=0	[3, 5, 8, 1, 2]
3	i=2, key=8	[3, 5, 8, 1, 2]	Compare 5 > 8	No shift	[3, 5, 8, 1, 2]
4	i=3, key=1	[3, 5, 8, 1, 2]	Compare 8 > 1	Shift 8 right	[3, 5, 8, 8, 2]
5	j=2	After shift	Compare 5 > 1	Shift 5 right	[3, 5, 5, 8, 2]
6	j=1	After shift	Compare 3 > 1	Shift 3 right	[3, 3, 5, 8, 2]
7	j=0 -> j=-1	After shifts	No more comparisons	Insert key at j+1=0	[1, 3, 5, 8, 2]
8	i=4, key=2	[1, 3, 5, 8, 2]	Compare 8 > 2	Shift 8 right	[1, 3, 5, 8, 8]
9	j=2	After shift	Compare 5 > 2	Shift 5 right	[1, 3, 5, 5, 8]
10	j=1	After shift	Compare 3 > 2	Shift 3 right	[1, 3, 3, 5, 8]
11	j=0	After shifts	Compare 1 > 2	No shift	[1, 3, 3, 5, 8]
12	Insert key at j+1=1	Final insert	N/A	Insert 2	[1, 2, 3, 5, 8]
13	i=5	Check loop condition	i < len(arr)? False	Stop	[1, 2, 3, 5, 8]

💡 i reaches 5 which is equal to array length, so loop ends and array is sorted

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 4	After Step 8	Final
i	1	1	2	3	4	5
key	3	3	8	1	2	N/A
j	0	-1	1	-1	0	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 directly?

We shift elements to the right to make space for the key. This is shown in steps 1, 4, 5, 6, 8, 9, and 10 where elements move right before inserting the key (see 'Shift' in execution_table).

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

When j is -1, it means we've checked all elements on the left. The key should be inserted at position 0 (j+1). This is shown in steps 2 and 7 where j goes to -1 and insertion happens.

Why do we compare arr[j] > key and not arr[j] >= key?

Using > ensures stable sorting by not moving equal elements unnecessarily. The execution_table comparisons always check '>' to decide shifts.

Visual Quiz - 3 Questions

Look at the execution table, what is the array state after step 7?

A [1, 3, 5, 8, 8]

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

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

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

💡 Hint

Check the 'Resulting Array' column at step 7 in the execution_table.

At which step does the key 2 get inserted into the array?

A Step 12

B Step 9

C Step 10

D Step 11

💡 Hint

Look for the step with 'Insert key' and key=2 in the execution_table.

If the array started as [5, 3, 8, 1, 2], what would be the value of j after the first shift when i=1?

A 0

B -1

C 1

D 2

💡 Hint

See step 2 in execution_table where j moves from 0 to -1 after shifting.

Concept Snapshot

Insertion Sort:
- Start from second element (i=1)
- Compare key with sorted left side
- Shift larger elements right
- Insert key at correct position
- Repeat until array sorted
- Stable, in-place sorting algorithm

Full Transcript

Insertion sort works by taking each element from the second position and inserting it into the correct place in the sorted part on the left. We compare the key with elements before it, shifting those larger than the key to the right to make space. When no more larger elements remain, we insert the key. This repeats until the entire array is sorted. The execution table shows each comparison, shift, and insertion step by step, tracking how the array changes. Variables i, j, and key control the process. Key moments clarify why shifting is used instead of swapping, why the inner loop stops at j=-1, and why the comparison uses greater than only. The visual quiz tests understanding of array states and variable values during sorting.

Practice

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

easy

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

B. Divide the list 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 a 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

   Options A, B, and D describe other sorting algorithms: bubble sort, merge sort, and selection sort respectively.

3. Final Answer:

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

4. Quick Check:

   Insertion sort = Insert elements in order [OK]

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

Common Mistakes:

• Confusing insertion sort with bubble sort
• Thinking insertion sort divides the list
• Mixing insertion sort with selection sort

2. Which of the following is the correct syntax to start the outer loop for insertion sort on a list arr of length n in Python?

easy

A. for i in range(0, n-1):

B. for i in range(n):

C. for i in range(1, n):

D. for i in range(n-1, 0, -1):

Solution

1. Step 1: Identify insertion sort loop start

   The outer loop starts from index 1 because the first element (index 0) is considered sorted.

2. Step 2: Check options

   for i in range(1, n): correctly uses range(1, n). Options B and C start from 0 which is incorrect. for i in range(n-1, 0, -1): loops backwards which is not standard for insertion sort.

3. Final Answer:

   for i in range(1, n): -> Option C

4. Quick Check:

   Start loop at 1 for insertion sort [OK]

Hint: Start outer loop from 1, not 0 [OK]

Common Mistakes:

• Starting loop at 0 instead of 1
• Using reverse loop incorrectly
• Confusing loop ranges

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

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

arr = [4, 3, 2, 1]
insertion_sort(arr)
print(arr)

medium

A. [4, 3, 2, 1]

B. [1, 2, 3, 4]

C. [1, 3, 2, 4]

D. [2, 3, 4, 1]

Solution

1. Step 1: Trace the insertion sort on input

   The list [4, 3, 2, 1] is sorted step-by-step by moving smaller elements leftwards until fully sorted.

2. Step 2: Final sorted list

   After sorting, the list becomes [1, 2, 3, 4].

3. Final Answer:

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

4. Quick Check:

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

Hint: Insertion sort outputs sorted ascending list [OK]

Common Mistakes:

• Assuming original list remains unchanged
• Confusing output with partial sorting
• Misreading the while loop condition

4. Find the error in the following insertion sort code:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i
        while j > 0 and arr[j-1] > key:
            arr[j] = arr[j-1]
            j -= 1
        arr[j] = key

arr = [3, 1, 2]
insertion_sort(arr)
print(arr)

medium

A. The for loop should start from 0, not 1

B. The while loop condition should be j >= 0, not j > 0

C. The assignment arr[j] = key should be outside the while loop

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

Solution

1. Step 1: Check initialization of j

   In insertion sort, j should start at i - 1 to compare the key with previous elements using the standard condition arr[j] > key.

2. Step 2: Verify other parts

   The while loop condition and assignment are correct. The for loop correctly starts at 1.

3. Final Answer:

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

4. Quick Check:

   j = i - 1 to compare previous elements [OK]

Hint: Start j at i-1 to compare with previous elements [OK]

Common Mistakes:

• Using j = i instead of standard j = i-1
• Changing while loop condition incorrectly
• Misplacing key assignment inside loop

5. Given a list arr = [5, 3, 8, 6, 2], how many total shifts (element moves) will insertion sort perform to sort the list in ascending order?

hard

A. 6

B. 8

C. 7

D. 5

Solution

1. Step 1: Trace shifts during sorting

   Insertion sort shifts elements to insert the key in the correct place:
   - i=1 (key=3): shift 5 right (1 shift)
   - i=2 (key=8): no shift (0 shifts)
   - i=3 (key=6): shift 8 right (1 shift)
   - i=4 (key=2): shift 8, 6, 5, 3 right (4 shifts)

2. Step 2: Calculate total shifts

   Total shifts = 1 + 0 + 1 + 4 = 6 shifts. But note that each shift moves one element one position right. Counting carefully:
   At i=1: 1 shift
   At i=3: 1 shift
   At i=4: 4 shifts
   Total = 6 shifts

3. Step 3: Recount carefully

   Actually, at i=4, elements 3,5,6,8 are shifted right one by one (4 shifts). Total shifts = 1 + 0 + 1 + 4 = 6.

4. Final Answer:

   6 -> Option A

5. Quick Check:

   Count shifts per insertion = 6 [OK]

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

Common Mistakes:

• Counting comparisons instead of shifts
• Missing multiple shifts in one insertion
• Confusing shifts with swaps