Week 5: Insertion Sort

BSCS1001 — IIT Madras BS Degree Prerequisite: Topic 09 (Lists & Collections) Cross-links: BSCS1002-Python (Week 7 — Sorting), BSCS2002-PDSA (Week 5 — Insertion Sort)

1. Motivation: Why Sort?

Real-world analogy: Finding a word in a dictionary. If the words weren't sorted, you'd have to check every page. Because they are sorted, you can flip to roughly the right spot.

2. The Insertion Sort Idea

"Repeatedly insert the next element into a sorted list." (Diagram)

Key Insight: The Invariant

• [] is sorted (trivially)
• Inserting into a sorted list produces a sorted list
• Therefore, after processing all elements, the result is sorted This is called a loop invariant — a property that holds true before and after each iteration.

3. Inserting into a Sorted List

The Algorithm

pseudo
Procedure SortedListInsert(L, x)
    newList = []
    inserted = False
    foreach z in L {
        if (not(inserted)) {
            if (x < z) {
                newList = newList ++ [x]
                inserted = True
            }
        }
        newList = newList ++ [z]
    }
    // If x is larger than everything, append at end
    if (not(inserted)) {
        newList = newList ++ [x]
    }
    return(newList)
End SortedListInsert

How It Works

1. Start with an empty new list
2. Iterate through the sorted list L
3. If we haven't inserted x yet, check if x should go before current z
4. If yes, insert x first, then z
5. If no, just add z
6. At the end, if x wasn't inserted (it's larger than all elements), append it

Tracing: Insert 5 into [3, 7, 9]

Boundary Cases

4. Full Insertion Sort Algorithm

The Main Algorithm

pseudo
Procedure InsertionSort(L)
    sortedList = []
    foreach z in L {
        sortedList = SortedListInsert(sortedList, z)
    }
    return(sortedList)
End InsertionSort

Complete Pseudocode (Both Procedures)

pseudo
Procedure SortedListInsert(L, x)
    newList = []
    inserted = False
    foreach z in L {
        if (not(inserted)) {
            if (x < z) {
                newList = newList ++ [x]
                inserted = True
            }
        }
        newList = newList ++ [z]
    }
    if (not(inserted)) {
        newList = newList ++ [x]
    }
    return(newList)
End SortedListInsert
Procedure InsertionSort(L)
    sortedList = []
    foreach z in L {
        sortedList = SortedListInsert(sortedList, z)
    }
    return(sortedList)
End InsertionSort

5. Step-by-Step Tracing

Sorting [7, 3, 9, 1]

• SortedListInsert([], 7): empty list, append 7
• sortedList = [7] Step 2: Take 3, insert into [7]
• L=[7], x=3: compare 3<7 → insert before 7
• sortedList = [3, 7] Step 3: Take 9, insert into [3, 7]
• 9<3? No. 9<7? No. End: append 9.
• sortedList = [3, 7, 9] Step 4: Take 1, insert into [3, 7, 9]
• 1<3? Yes → insert before 3
• sortedList = [1, 3, 7, 9]

Complete Tracing Table

Another Example: [5, 2, 8, 2, 9]

6. Boundary Conditions

Case 1: Empty List

pseudo
InsertionSort([])

Case 2: Single Element

pseudo
InsertionSort([5])

Case 3: Already Sorted

pseudo
InsertionSort([1, 2, 3, 4])

Case 4: Reverse Sorted (Worst Case)

pseudo
InsertionSort([4, 3, 2, 1])

7. Recursive Insertion Sort

pseudo
Procedure InsertionSortRec(L)
    if (length(L) <= 1) {
        return(L)
    }
    else {
        // Sort rest of list, then insert first element
        return(SortedListInsert(
            InsertionSortRec(rest(L)),
            first(L)
        ))
    }
End InsertionSortRec

How It Works

1. InsertionSortRec([7, 3, 9, 1])
2. → SortedListInsert(InsertionSortRec([3, 9, 1]), 7)
3. → → SortedListInsert(SortedListInsert(InsertionSortRec([9, 1]), 3), 7)
4. → → → continues until base case

8. Complexity Analysis

Time Complexity

Space Complexity

Comparison with Other Sorts

Note: Insertion sort is not the fastest, but it's the simplest and works well for small or nearly-sorted lists.

9. Comparison: Sorting Approaches

Insertion Sort vs Other Simple Sorts

When to Use Insertion Sort

10. Practice Questions

Basic Questions

Show Answer

Insertion sort repeatedly takes the next element from the original list and inserts it into the correct position in a new sorted list. The invariant is that the new list is always sorted. Q2. Trace insertion sort on [4, 1, 3]. Show the sorted list after each step. Show Answer

Final: [1, 3, 4] Q3. What happens in SortedListInsert when x is larger than all elements in L? Show Answer

The inserted flag stays False throughout the loop. After the loop, the check if (not(inserted)) is True, so x is appended at the end. Q4. What is the best-case input for insertion sort? What is the time complexity? Show Answer

Best case: An already-sorted list. Each element just gets appended (no shifting needed). Time complexity: O(N).

Intermediate Questions

Show Answer

Result: [2, 5, 6, 8] Q6. Trace the full insertion sort on [9, 5, 7]. Show Answer

Final: [5, 7, 9] Q7. What is a loop invariant? What is the loop invariant of insertion sort? Show Answer

A loop invariant is a property that holds true before and after each iteration of a loop.

For insertion sort, the invariant is: After processing k elements, the sorted list contains those k elements in sorted order. This is true at the start (empty list is sorted), remains true after each insertion, and when all N elements are processed, the full list is sorted. Q8. How would you sort a list in descending order using insertion sort? Show Answer

Change the comparison in SortedListInsert from x < z to x > z:

sql
if (x > z) {    // Changed from < to >
    newList = newList ++ [x]
    inserted = True
}

This inserts larger elements before smaller ones, producing descending order.

Advanced Questions

Show Answer

Adaptive means the algorithm performs better when the input is partially sorted (has existing order). Insertion sort is adaptive because:

• For an already-sorted list, each insertion just appends (O(N))
• For a nearly-sorted list, few elements need to be shifted far
• The number of comparisons equals the number of inversions (out-of-order pairs)

This makes insertion sort excellent for "almost sorted" data. Q10. Compare insertion sort with selection sort. Which is better and when? Show Answer

When to use: Insertion sort for small or nearly-sorted data; selection sort when writes are expensive (e.g., EEPROM). Q11. Trace insertion sort on [3, 1, 4, 1, 5, 9, 2, 6] for the first 4 elements only. Show Answer

After 4 elements: [1, 1, 3, 4] Q12. Write a version of insertion sort that sorts a list of student records by their Maths marks (ascending). Show Answer

pseudo
Procedure InsertionSortByMarks(L)
    sortedList = []
    foreach z in L {
        sortedList = SortedListInsertByMarks(sortedList, z)
    }
    return(sortedList)
End InsertionSortByMarks

Procedure SortedListInsertByMarks(L, x)
    newList = []
    inserted = False
    foreach z in L {
        if (not(inserted)) {
            if (x.Maths < z.Maths) {     // Compare Maths field
                newList = newList ++ [x]
                inserted = True
            }
        }
        newList = newList ++ [z]
    }
    if (not(inserted)) {
        newList = newList ++ [x]
    }
    return(newList)
End SortedListInsertByMarks

📚 Cross-References

Next Topic: 11 — Dictionaries

Quiz Tip: Insertion sort tracing questions are very common. Practice with different inputs until you're fast! Join Discord PreviousLists & CollectionsNextDictionaries