Source: Comprehensive Guide to Sorting Algorithms, Computer Science I (UCF)
Tags: HeapSort, MergeSort, QuickSort, divide and conquer, partitioning, pivot, max heap, binary heap, heapify, merge, recurrence relation, O(n log n), space complexity, algorithm comparison, CS 101, computer science fundamentals
Difficulty: Intermediate. Prerequisites: Part 1 notes (sorting problem definition, Big-O basics, simple O(n²) sorts).
Part 1 covered three O(n²) sorts that work fine on small inputs but collapse on large ones. This set of notes introduces three algorithms that bring the worst or average case down to O(n log n): HeapSort, MergeSort, and QuickSort. Each uses a different strategy to get there, and the trade-offs between them (stability, space, worst-case guarantees, real-world speed) are a staple of CS exams and technical interviews alike.
These notes also include a side-by-side comparison of all six algorithms, plus the space-complexity and practical considerations that determine which sort you would choose in a real system.
HeapSort, MergeSort, and QuickSort all achieve O(n log n) average-case time. MergeSort guarantees O(n log n) in every case but needs O(n) extra space. HeapSort guarantees O(n log n) in-place. QuickSort is the fastest in practice on average but can degrade to O(n²) with a bad pivot. Choosing between them depends on whether you need stability, have memory constraints, or can tolerate a probabilistic worst case.
Divide and conquer
An algorithm-design paradigm that breaks a problem into smaller subproblems of the same type, solves each recursively, and combines the results. Think of it as "split, solve the pieces, glue the answers back together."
Max heap
A complete binary tree stored in an array where every parent node is greater than or equal to its children. In simple terms, the largest element always sits at the root (index 0).
Heapify (sift down)
The operation that restores the heap property after the root has been replaced. It compares the root with its children and swaps downward until the tree satisfies the max-heap rule again.
Pivot (QuickSort)
The element chosen to partition the array. Everything less than or equal to the pivot goes to one side; everything greater goes to the other. The quality of the pivot choice determines QuickSort's performance.
Partitioning
Rearranging an array around a pivot so that smaller elements precede the pivot and larger elements follow it. After partitioning, the pivot is in its final sorted position.
Recurrence relation
An equation that defines a function in terms of its value on smaller inputs, such as T(n) = 2T(n/2) + O(n). Solving it gives the overall time complexity.
Stable sort
A sort that preserves the original relative order of elements with equal keys. Of the three efficient sorts here, only MergeSort is stable in its standard implementation.
External sort
A sorting strategy for data too large to fit in memory, typically reading and writing chunks to disk. MergeSort's merge step adapts naturally to this setting.
Build a max heap from the input array. This takes O(n) time using the bottom-up heapify approach.
The root of the heap is now the largest element. Swap it with the last element in the array.
Shrink the heap size by one (the last position is now "sorted").
Heapify the new root to restore the max-heap property.
Repeat the extract-swap-heapify cycle until the heap is empty.
The result is a fully sorted array, built from the back (largest element placed last, then second-largest, and so on).
Worst case: O(n log n).
Average case: O(n log n).
Best case: O(n log n). HeapSort does not shortcut on favourable inputs.
Space: O(1) extra. It sorts entirely in place.
Stability: not stable.
HeapSort's guaranteed O(n log n) with O(1) space makes it attractive when memory is tight and you need a hard upper bound on runtime.
The algorithm follows three steps:
Divide: Split the array in half recursively until each subarray contains a single element (the base case).
Conquer: Each single-element subarray is trivially sorted.
Combine: Merge pairs of sorted subarrays into larger sorted subarrays by comparing their front elements, always appending the smaller one to the result, and advancing that pointer.
Worked example with [2, 14, −4, 19, −5, 0, 8, 3]:
Split into [2, 14, −4, 19] and [−5, 0, 8, 3].
Each half splits again, down to single elements.
Merge upward: single elements into sorted pairs, sorted pairs into sorted quads, sorted quads into the final sorted array [−5, −4, 0, 2, 3, 8, 14, 19].
The recurrence is T(n) = 2T(n/2) + O(n).
This solves to O(n log n) in all cases (worst, average, best).
Space: O(n) extra, because the merge step needs a temporary array to hold the merged result.
Stability: stable (equal elements retain their original order during the merge).
MergeSort's consistent O(n log n) and stability make it the standard choice for external sorting (data on disk) and for languages that guarantee a stable sort in their standard library.
Maintain a pointer at the start of each of the two sorted subarrays.
Compare the elements at both pointers.
Copy the smaller element into the output and advance that pointer.
When one subarray is exhausted, copy the remainder of the other.
The merge of two subarrays totalling n elements takes O(n) time.
Partition: Choose a pivot element. Rearrange the array so that all elements ≤ pivot are on its left and all elements > pivot are on its right. The pivot is now in its final sorted position.
Recurse: Apply the same process to the left subarray and the right subarray.
Combine: Nothing to do; the partitioning has already placed everything correctly.
Worked example with [19, 0, 3, −4, −5, 14, 2, 8], choosing pivot = 14:
After partitioning: elements ≤ 14 are on the left, elements > 14 on the right, and 14 sits between them.
Recursively sort the left and right portions.
Average case: O(n log n). Achieved when the pivot splits the array into roughly equal halves.
Best case: O(n log n), with balanced partitions.
Worst case: O(n²). Occurs when the pivot is consistently the smallest or largest element (e.g., already-sorted input with a naive "pick the first element" strategy).
Space: O(log n) average for the recursion stack; O(n) in the worst case if partitions are maximally unbalanced.
Stability: not stable in its standard in-place form.
Despite the O(n²) worst case, QuickSort is often the fastest sort in practice. Its inner loop is very cache-friendly, and randomised pivot selection makes the worst case extremely unlikely.
The pivot choice is the single biggest factor in QuickSort's performance:
First or last element: simple, but vulnerable to O(n²) on sorted or nearly sorted input.
Random element: the most common practical fix; expected O(n log n) regardless of input order.
Median-of-three (first, middle, last): a good balance of simplicity and reliability.
Algorithm | Best Case | Average Case | Worst Case | Space | Stable? |
|---|---|---|---|---|---|
BubbleSort | O(n) | O(n²) | O(n²) | O(1) | Yes |
InsertionSort | O(n) | O(n²) | O(n²) | O(1) | Yes |
SelectionSort | O(n²) | O(n²) | O(n²) | O(1) | No |
HeapSort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
MergeSort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
QuickSort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
T(n) = 2T(n/2) + O(n), which solves to T(n) = O(n log n).
The 2T(n/2) term comes from sorting two halves; the O(n) term comes from the merge step, which touches every element once.
Most standard-library sort functions in modern languages are hybrid algorithms: Python's Timsort and Java's Arrays.sort both use MergeSort-style merging for large runs and InsertionSort for small subarrays. The C standard library's qsort is typically a QuickSort variant with median-of-three pivoting and a fallback to HeapSort if recursion depth gets too deep (this hybrid is called Introsort).
HeapSort's in-place O(n log n) guarantee makes it useful as a safety net inside these hybrids, and the heap data structure itself shows up in priority queues, schedulers, and graph algorithms like Dijkstra's.
Students often believe QuickSort is always O(n log n). It is not; the worst case is O(n²). Randomised pivot selection makes the worst case unlikely, but it can still happen.
Students often think MergeSort is in-place. The standard implementation requires O(n) additional space for the temporary merge array. In-place merge sort variants exist but are complex and rarely used in practice.
Students sometimes assume HeapSort is related to MergeSort because both are O(n log n). They use entirely different strategies: HeapSort relies on a heap data structure, while MergeSort uses recursive splitting and merging.
Students sometimes forget that "building the heap" is O(n), not O(n log n). The bottom-up heapify process takes linear time, which is a common exam detail.
⚠️ Know the full comparison table (all six algorithms, all three cases, space, stability) from memory. This is one of the most frequently tested pieces of the entire course.
⚠️ Be able to trace MergeSort's split-and-merge process on a short array and show the state at each level of recursion.
⚠️ Be able to trace QuickSort's partitioning step given a specific pivot. Exam questions often ask "show the array after partitioning around pivot X."
⚠️ Understand why MergeSort needs O(n) extra space while HeapSort does not. The merge step writes into a separate array; HeapSort rearranges elements within the original array.
⚠️ Be prepared to explain when you would choose one sort over another. Typical question: "You have a memory-constrained embedded system with unpredictable input. Which sort and why?" (HeapSort: O(n log n) guaranteed, O(1) space.)
⚠️ QuickSort's worst case on already-sorted input with a naive pivot is a classic exam trap.
True or false: MergeSort's worst-case time complexity is O(n²).
Fill in the blank: HeapSort uses a ______ data structure to organise elements.
True or false: QuickSort is a stable sorting algorithm.
Fill in the blank: The recurrence relation for MergeSort is T(n) = 2T(n/2) + ______.
True or false: HeapSort requires O(n) additional space.
Answers: 1) False (it is O(n log n)). 2) Max heap (binary heap). 3) False. 4) O(n). 5) False (it sorts in place with O(1) extra space).
Q: Explain the three steps of the divide-and-conquer paradigm as applied to MergeSort.
A: Divide: split the array in half recursively until each piece is a single element. Conquer: single elements are already sorted. Combine: merge pairs of sorted subarrays by repeatedly taking the smaller front element from each pair, producing a larger sorted subarray.
Q: Why does QuickSort have a worst-case time complexity of O(n²), and how can this be mitigated?
A: The worst case occurs when every partition is maximally unbalanced, for instance when the pivot is always the smallest or largest element. This produces n levels of recursion with O(n) work at each level. Using randomised pivot selection or median-of-three makes balanced partitions overwhelmingly likely, reducing the expected time to O(n log n).
Q: A system requires a guaranteed O(n log n) sort with no extra memory allocation. Which algorithm fits, and why?
A: HeapSort. It runs in O(n log n) in all cases and sorts in place, needing only O(1) extra space. MergeSort guarantees O(n log n) but needs O(n) extra space; QuickSort uses little extra space on average but does not guarantee O(n log n).
Q: Why is MergeSort preferred for external sorting (data that does not fit in memory)?
A: MergeSort's merge step reads two sorted streams sequentially and writes one sorted stream. This pattern maps well to sequential disk access, which is far faster than random access. The algorithm also guarantees O(n log n) regardless of input order, which is important when you cannot afford a worst-case blowup on data stored on slow media.
Q: Given the array [5, 3, 8, 1, 2], perform one full partition step using the last element (2) as the pivot. What does the array look like after partitioning?
A: After partitioning around pivot 2: [1, 2, 8, 5, 3] (or any arrangement where 1 is to the left of 2 and all elements greater than 2 are to the right). The pivot, 2, is now in its final sorted position at index 1.
Q: Compare the space requirements of MergeSort, HeapSort, and QuickSort.
A: MergeSort uses O(n) extra space for the temporary merge array. HeapSort uses O(1) extra space because it rearranges elements in the original array. QuickSort uses O(log n) space on average for the recursion stack, but O(n) in the worst case if partitions are highly unbalanced.
The divide-and-conquer pattern from MergeSort and QuickSort reappears in many other algorithms: binary search, Strassen's matrix multiplication, and the closest-pair-of-points problem, among others. Recognising the "split, recurse, combine" structure is one of the most transferable skills from this unit.
The heap data structure from HeapSort is the foundation of priority queues, which in turn power Dijkstra's shortest-path algorithm and Huffman coding. If you understand heapify, you already understand the core operation behind all of these.
The space-versus-time trade-off visible in MergeSort (fast and stable, but needs extra memory) versus HeapSort (fast and in-place, but not stable) is a recurring theme across all of computer science.
HeapSort, heap sort, MergeSort, merge sort, QuickSort, quick sort, divide and conquer, partitioning, pivot selection, median-of-three, randomised pivot, max heap, binary heap, heapify, sift down, merge procedure, recurrence relation, T(n) = 2T(n/2) + O(n), O(n log n), stable sort, external sort, Introsort, Timsort, in-place sort, recursion stack, algorithm comparison, sorting complexity table, CS 101 sorting, UCF Computer Science I