COMP5112 Chap.9 Merge Sort, Quick Sort and Recurrences
Merge Sort, Quick Sort and Recurrences
Recursion shape explains the bound
Merge sort and quick sort both divide arrays and recurse, but merge sort spends linear work combining sorted halves while quick sort spends linear work partitioning before the calls. The chapter expands recurrences, tracks merge indices, states partition-zone invariants and connects pivot rules to balanced or chain-shaped recursion.
It also compares stability, storage and worst-case guarantees.
Merge sort divides an array into halves until subarrays have at most one item. On return, it merges two already sorted runs. Maintain one cursor per run, copy the smaller current key, and advance only that cursor. Once a run is exhausted, append the other tail.
The output-prefix invariant says that copied items are sorted and are exactly the smallest consumed inputs. Taking ties from the left run preserves stability.
Balanced division gives the recurrence T of n equals two T of n divided by two plus linear merge work. At each recursion depth the subproblem sizes sum to n, so one level performs linear work.
Halving creates logarithmically many non-base levels, yielding n log n total time. The base case and uneven split rounding affect constants rather than the asymptotic conclusion.
Quick sort partitions before recursive calls. A pivot rule and partition scheme determine the zone invariant and the returned boundary.
In a final-pivot scheme, processed keys at or below the pivot accumulate on one side and larger keys on the other before the pivot reaches its final position. Other schemes return a split rather than a final pivot position. Recursive bounds must match the exact contract so ranges shrink and never overlap incorrectly.
Partition balance controls recursion shape.
Roughly equal sides give two subproblems whose total work per level is linear across logarithmic depth. Repeatedly choosing an extreme pivot produces one subproblem of size n minus one and linear partition work at each level, summing to quadratic time.
Sorted input is dangerous only for pivot rules that systematically choose an extreme; algorithm version and input arrangement must be stated together.
Random pivot selection gives expected O of n log n time for each fixed input by making persistent extreme choices unlikely. It does not remove the quadratic worst case, and it is not the same as average-case analysis over a distribution of input arrays.
Name what randomness is averaged. Security-sensitive or hard real-time work may value a deterministic guarantee differently from strong expected performance.
The algorithms trade properties. Standard merge sort offers predictable n log n time and can be stable, commonly using linear temporary array space. Array quick sort is usually unstable, often has strong locality, and uses recursion space tied to partition balance.
A comparison should attach storage, stability and time claims to specified implementations. Expanding a few recurrence levels and tracing two-element, all-equal and reverse-order inputs exposes boundary mistakes before a memorised theorem is applied.
What this chapter covers
- 01
Divide and conquer phases
- 02
Two-index merging
- 03
Merge-sort recurrence
- 04
Partition invariants
- 05
Quick-sort pivot balance
- 06
Best, expected and worst cases
Worked example · free
Merge two sorted runs
- 3Compare the two active fronts.
- 2Advance only the copied side.
- 2Append the unexhausted remainder.
Key terms
- Recurrence
- An equation expressing running time through smaller instances and local work.
- Partition
- A rearrangement separating keys according to a pivot relation.
- Pivot
- The key used to divide a quick-sort subarray.
- Expected Time
- Average running time over the algorithm's random choices under the stated model.
Merge Sort, Quick Sort and Recurrences FAQ
Why is merge sort O(n log n)?
Balanced halving creates logarithmically many levels, and merging across all calls on each level processes O(n) items, giving O(n log n) total work after the base cases are included.
When does quick sort reach quadratic time?
When the pivot rule repeatedly produces a subproblem of size n minus one and another of size zero. Sorted input is bad only for pivot rules that make it repeatedly extreme.
Does randomisation remove quick sort's worst case?
No. It lowers the probability of repeatedly choosing extreme pivots and gives good expected behaviour, while the worst-case bound remains quadratic for a sufficiently unlucky sequence of pivot choices.
Exam move
Draw two recursion levels and write total local work on each. For quick sort, label partition zones and recursive boundaries before calculating a recurrence. Trace merge cursors on unequal run lengths and labelled duplicates, then verify stability from the tie rule. Test partition pseudocode on two-element, all-equal and already ordered arrays.
For each recurrence, describe the recursion shape in words before summing its level costs and naming best, expected or worst case.
Working through Merge Sort, Quick Sort and Recurrences in COMP5112? Sia is AskSia’s AI Computer Science tutor — ask any COMP5112 Merge Sort, Quick Sort and Recurrences question and get a clear, step-by-step explanation grounded in how COMP5112 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
