Insertion Sort Algorithm in DSA Python

Mental Model

Insertion sort builds a sorted list by taking one item at a time and placing it in the right spot among the items already sorted.

Analogy: Imagine sorting playing cards in your hand by picking one card and inserting it into the correct position among the cards you already hold sorted.

Unsorted array: [5, 3, 8, 4, 2]
Sorted part ↑
[5] [3] [8] [4] [2]
 ↑

Dry Run Walkthrough

Input: list: [5, 3, 8, 4, 2]

Goal: Sort the list in ascending order using insertion sort

Step 1: Take second element (3) and compare with first (5), then insert 3 before 5

[3, 5, 8, 4, 2]

Why: We place 3 before 5 to keep the first two elements sorted

Step 2: Take third element (8), compare with 5, stays in place

[3, 5, 8, 4, 2]

Why: 8 is greater than 5, so it stays at its position

Step 3: Take fourth element (4), compare with 8 and 5, insert before 5

[3, 4, 5, 8, 2]

Why: 4 is less than 5 and 8, so it moves left to keep sorted order

Step 4: Take fifth element (2), compare with 8, 5, 4, 3, insert at start

[2, 3, 4, 5, 8]

Why: 2 is smallest, so it moves all the way to the front

Result:

[2, 3, 4, 5, 8]

Annotated Code

DSA Python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]  # current element to insert
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # shift element right
            j -= 1  # move left to find correct spot
        arr[j + 1] = key  # insert key at correct position


# Driver code
arr = [5, 3, 8, 4, 2]
insertion_sort(arr)
print(arr)

for i in range(1, len(arr)):

iterate over each element starting from second to insert it

key = arr[i] # current element to insert

store the element to be inserted in sorted part

while j >= 0 and arr[j] > key:

shift elements greater than key to the right to make space

arr[j + 1] = arr[j] # shift element right

move element one position right

j -= 1 # move left to find correct spot

move left to continue checking

arr[j + 1] = key # insert key at correct position

place key in its sorted position

Output

[2, 3, 4, 5, 8]

Complexity Analysis

Time: O(n^2) because in the worst case each element is compared with all previous elements

Space: O(1) because sorting is done in place without extra storage

vs Alternative: Compared to bubble sort, insertion sort is often faster on nearly sorted data because it stops early when elements are in order

Edge Cases

empty list

function returns immediately with no changes

DSA Python

for i in range(1, len(arr)):

list with one element

no changes needed, list remains same

DSA Python

for i in range(1, len(arr)):

list already sorted

minimal shifts, algorithm runs faster

DSA Python

while j >= 0 and arr[j] > key:

When to Use This Pattern

When you need to sort a small or nearly sorted list, insertion sort is a good choice because it inserts elements one by one in order.

Common Mistakes

Mistake: Not shifting elements to the right before inserting the key
Fix: Make sure to move elements greater than key one position right before placing key

Mistake: Inserting key at wrong index after shifting
Fix: Insert key at position j + 1 after shifting elements

Summary

Insertion sort builds a sorted list by inserting each element into its correct position.

Use it for small or nearly sorted lists where simple sorting is efficient.

The key insight is shifting larger elements right to make space for the current element.

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