Which sorting algorithm is NOT typically O(n log n) on average?

Which sorting algorithm is NOT typically O(n log n) on average?

• A. QuickSort – O(n log n) on average
• B. MergeSort – O(n log n) on average
• C. HeapSort – O(n log n) on average
• D. InsertionSort – O(n^2) on average

Answer: (D)

The key idea is how the number of operations grows with the input size for each sorting method. Insertion sort builds the final order one element at a time by inserting each new element into its correct position within the already-sorted prefix. To place the i-th element, you often have to compare and shift many of the previously seen elements. On average, about i/2 elements get moved for each insertion, and summing over i from 1 to n gives proportional to n^2 operations. That quadratic growth means it is not typically O(n log n). In contrast, the other three methods achieve O(n log n) on average because their work scales more efficiently. QuickSort partitions the data into two roughly equal parts and recursively sorts them; with an average balanced split, each level costs O(n) and there are about log n levels. MergeSort also splits in half each time and merges in linear time per level, yielding O(n log n) overall. HeapSort builds a heap and then repeatedly extracts the maximum (or minimum), with each extraction costing O(log n), for a total of O(n log n). So the one that isn’t typically O(n log n) on average is the insertion-based approach, which has quadratic average-case time.

The key idea is how the number of operations grows with the input size for each sorting method. Insertion sort builds the final order one element at a time by inserting each new element into its correct position within the already-sorted prefix. To place the i-th element, you often have to compare and shift many of the previously seen elements. On average, about i/2 elements get moved for each insertion, and summing over i from 1 to n gives proportional to n^2 operations. That quadratic growth means it is not typically O(n log n).

In contrast, the other three methods achieve O(n log n) on average because their work scales more efficiently. QuickSort partitions the data into two roughly equal parts and recursively sorts them; with an average balanced split, each level costs O(n) and there are about log n levels. MergeSort also splits in half each time and merges in linear time per level, yielding O(n log n) overall. HeapSort builds a heap and then repeatedly extracts the maximum (or minimum), with each extraction costing O(log n), for a total of O(n log n).

So the one that isn’t typically O(n log n) on average is the insertion-based approach, which has quadratic average-case time.