An array of 1,000 elements has exactly 5 elements out of place. Which sorting algorithm will likely perform closest to O(n) on this input?
AMerge sort, because it is always O(n log n) regardless of input
BInsertion sort, because nearly-sorted arrays have few inversions and it removes exactly one inversion per operation
CSelection sort, because it scans linearly and skips sorted regions
DHeap sort, because its heapify step is optimized for small perturbations
Insertion sort's running time is proportional to the number of inversions in the array — pairs (i,j) where i<j but a[i]>a[j]. With only 5 elements out of place, there are at most O(n) inversions, so insertion sort runs in O(n) time on this input. Merge sort and heap sort always take O(n log n) regardless of sortedness. Selection sort is always O(n²) because it must find the minimum each pass. This is also why hybrid sorts like Timsort switch to insertion sort when subarrays become small or nearly sorted.
Question 2 Multiple Choice
Why do real-world sorting libraries like Python's Timsort often switch to insertion sort for subarrays smaller than about 64 elements, even though insertion sort is O(n²)?
AInsertion sort has lower memory usage than merge sort, which is the bottleneck at small sizes
BInsertion sort is stable and Timsort requires stability throughout
CAt small n, insertion sort's low constant factors and cache-friendly sequential access beat the overhead of recursive O(n log n) algorithms
DInsertion sort is parallelizable in ways merge sort is not
Big-O notation hides constant factors. Merge sort requires recursive function calls, auxiliary memory allocation, and non-sequential memory access — overhead that costs more than the algorithmic savings when n is small. Insertion sort scans sequentially, shifts elements in-place, and has almost no bookkeeping overhead. At n=16, O(n²) with tiny constants beats O(n log n) with large constants. Stability is a real property of insertion sort, but it is not why Timsort uses it for small subarrays — the primary reason is constant-factor performance.
Question 3 True / False
Insertion sort runs in O(n) time when the input array is already sorted.
TTrue
FFalse
Answer: True
When the array is already sorted, each element is compared once against its left neighbor, finds it is already in place, and moves on with no shifts. The total work is exactly n-1 comparisons — O(n). This is the zero-inversion case: a sorted array has no inversions, and insertion sort does work proportional to the number of inversions. The O(n) best case is unique among simple sorting algorithms — selection sort is always O(n²) because it must scan for the minimum each pass regardless of input order.
Question 4 True / False
Insertion sort is typically slower in practice than merge sort or quicksort, because those algorithms have better asymptotic complexity.
TTrue
FFalse
Answer: False
Asymptotic notation describes growth rate, not actual speed for all inputs. Insertion sort outperforms merge sort and quicksort in two important real-world cases: (1) very small arrays (n < ~64), where insertion sort's constant factors are much lower than the recursive overhead of divide-and-conquer algorithms; and (2) nearly-sorted data, where insertion sort approaches O(n) while merge sort stays at O(n log n). This is why production sorting libraries routinely use insertion sort as the base case in hybrid algorithms — it is faster in practice for exactly these common scenarios.
Question 5 Short Answer
What is the relationship between the number of inversions in an array and the amount of work insertion sort performs? Why does this explain its O(n) best case and O(n²) worst case?
Think about your answer, then reveal below.
Model answer: An inversion is a pair (i,j) where i<j but a[i]>a[j] — an element that is ahead of something it should follow. Each comparison-and-shift in insertion sort eliminates exactly one inversion. A sorted array has zero inversions, so insertion sort finishes in O(n) time (only n-1 comparisons needed to verify). A reverse-sorted array of n elements has n(n-1)/2 inversions — the maximum — so insertion sort does O(n²) work. Any nearly-sorted array with only k inversions runs in O(n+k) time.
The inversion-counting perspective makes insertion sort's behavior precise rather than a vague claim that 'sorted inputs are fast.' It also connects to broader sorting theory: any algorithm that eliminates exactly one inversion per comparison cannot sort a worst-case input in fewer than O(n²) comparisons. Escaping this bound requires strategies like merge sort, which eliminates many inversions per step by merging sorted halves.