Insertion Sort Algorithm in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Insertion Sort Algorithm?

Insertion Sort builds the final sorted list one item at a time by taking each element and inserting it into its correct position among the already sorted elements.

beginner

How does Insertion Sort handle the elements during sorting?

It divides the list into a sorted and an unsorted part. It takes elements from the unsorted part and inserts them into the correct position in the sorted part by shifting larger elements to the right.

intermediate

What is the time complexity of Insertion Sort in the worst case?

The worst-case time complexity is O(n²), where n is the number of elements. This happens when the list is sorted in reverse order and every element must be compared and shifted.

beginner

Show the step-by-step insertion of the element 5 into the sorted list [1, 3, 7, 9].

To insert 5: Compare with 9 (shift 9 right), compare with 7 (shift 7 right), compare with 3 (stop, 5 > 3). Insert 5 after 3. Result: [1, 3, 5, 7, 9].

intermediate

Why is Insertion Sort efficient for nearly sorted lists?

Because it only shifts elements when necessary, if the list is almost sorted, few shifts are needed, making the algorithm run close to O(n) time.

What part of the list does Insertion Sort consider sorted at the start?

A The first element

B The last element

C The middle element

D The entire list

Insertion Sort starts with the first element as the sorted part and inserts other elements into it.

What happens when the current element is smaller than elements in the sorted part?

A It is swapped with the first element

B Elements larger than it are shifted right to make space

C The list is reversed

D The element is ignored

Larger elements are shifted right to insert the current element in the correct position.

What is the best-case time complexity of Insertion Sort?

A O(n²)

B O(n log n)

C O(n)

D O(log n)

When the list is already sorted, Insertion Sort only compares each element once, resulting in O(n) time.

Which of these is a characteristic of Insertion Sort?

A It builds the sorted list by inserting elements one by one

B It sorts by repeatedly swapping adjacent elements

C It is a divide and conquer algorithm

D It uses extra space proportional to the input size

Insertion Sort builds the sorted list by inserting elements one at a time.

For which type of list is Insertion Sort most efficient?

A Randomly ordered list

B Large unsorted list

C Reverse sorted list

D Nearly sorted list

Insertion Sort is efficient for nearly sorted lists because it requires fewer shifts.

Explain how Insertion Sort works step-by-step on a small list.

Think about how you sort playing cards in your hand.

Describe the time complexity of Insertion Sort and when it performs best and worst.

Consider how many shifts happen in different list orders.

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