Data Structures & Big-O (CS 201) · Module 7 of 9
Sorting Algorithms Compared
Merge sort, quicksort, and heap sort: their guarantees, their trade-offs, and when to reach for each.
Merge Sort
- Merge sort recursively divides the array in half, sorts each half, then merges the two sorted halves, guaranteeing O(n log n) time in all cases: best, average, and worst.
- Merge sort is stable, preserving the relative order of equal elements, but requires O(n) additional memory for the merge step, making it not in-place.
Why does merge sort guarantee O(n log n) performance even in the worst case, unlike quicksort?
Solution. Merge sort always splits the array exactly in half regardless of the input's order, so its recursion depth and merging work are consistent and don't depend on the data's arrangement, unlike quicksort's pivot-dependent partitioning.
Quicksort
- Quicksort partitions the array around a pivot — elements less than the pivot to one side, greater to the other — then recursively sorts each partition; average case is O(n log n), but worst case is O(n²) with consistently poor pivot choices.
- Quicksort is typically in-place, needing only O(log n) additional stack space on average — though this can grow to O(n) in the worst case (matching its O(n²) time worst case) unless the implementation always recurses into the smaller partition first. It's often faster in practice than merge sort due to better cache performance and smaller constant factors, despite the worse worst-case complexity.
Under what circumstances does quicksort degrade to its worst-case O(n²) performance?
Solution. When the chosen pivot consistently results in very unbalanced partitions, such as always picking the smallest or largest element as the pivot, which happens with a naive first-element pivot on an already-sorted array.
Heap Sort Revisited
- Heap sort guarantees O(n log n) in all cases and is in-place, but it is not stable and generally has worse practical performance — larger constant factors, poorer cache locality — than quicksort.
If heap sort guarantees O(n log n) worst-case and is in-place, why isn't it always preferred over quicksort?
Solution. In practice, heap sort tends to have worse cache performance, since its array-index-based tree structure causes more scattered memory access, and larger constant factors than quicksort, making quicksort often faster despite quicksort's theoretically worse worst-case complexity.
Choosing a Sorting Algorithm
- Choose merge sort when stability and a guaranteed worst case matter, especially for linked lists or external sorting where data is too large for memory.
- Choose quicksort for general-purpose, in-memory sorting with good average performance; choose heap sort when a strict O(n log n) worst-case and in-place memory usage matter more than raw speed.
Why might merge sort be preferred over quicksort for sorting a linked list specifically?
Solution. Merge sort's merge step works well with sequential access, which linked lists provide naturally, and doesn't require random access to elements, while quicksort's partitioning typically relies on efficient random access, which arrays provide but linked lists do not.
Check yourself
2 of this module's 5 quiz questions. Pick your answers, then check them in the app, with an explanation for every question.
1. What is merge sort's time complexity in the worst case?
2. Why is quicksort's worst case O(n²)?