Unit 4 Cycle 2 Day 8: Insertion Sort: Worst Case Count
Share
Insertion Sort: Worst Case Count
Section 4.7 — Sorting
Key Concept
Insertion sort's worst case occurs when the array is sorted in reverse order. Each element must be shifted past every previously sorted element, resulting in 1 + 2 + 3 + ... + (n-1) = n(n-1)/2 total shifts. The best case is an already-sorted array, requiring 0 shifts and only n-1 comparisons. The AP exam tests your understanding of these cases and asks you to count the exact number of comparisons or shifts for a specific input array, not just the big-O complexity.
Consider insertion sort on a reverse-sorted array.
How many total element shifts does insertion sort perform?
Answer: (B) 10
Pass 1: 1 shift. Pass 2: 2 shifts. Pass 3: 3 shifts. Pass 4: 4 shifts. Total: 1+2+3+4 = 10 = n(n-1)/2.
Why Not the Others?
(A) 4 is only the shifts in the final pass.
(C) 5 is the element count, not shift count.
(D) 20 does not match n(n-1)/2 for n=5.
Common Mistake
Reverse-sorted is the worst case for insertion sort: every element shifts past all previously sorted elements. Total = n(n-1)/2.
AP Exam Tip
Worst case insertion sort: reverse-sorted, O(n^2). Best case: already sorted, O(n). Know both.