Skip to main content

Mergesort Is the Divide-and-Conquer Exemplar

What This Concept Is​

Mergesort sorts two smaller regions and merges them. For a balanced split and linear merge work, T(n) = T(floor(n/2)) + T(ceil(n/2)) + Theta(n), with constant base cases. This is Theta(n log n) for n at least 2. A standard array version uses O(n) auxiliary slots; top-down recursion also needs O(log n) stack frames.

During merging, the output prefix contains the smallest consumed records in sorted order, and each unread suffix remains sorted. Pick the smaller head. On equal keys pick the left head to preserve stability.

Why It Matters Here​

The merge step separates two obligations: sortedness and preserving every input record exactly once. A program that drops duplicates can pass a sortedness-only test. Tagged payloads make stability and multiplicity observable. Bottom-up mergesort also provides a clean route to buffered run merging later.

Concrete Examples​

Merge (1,A),(3,B) with (1,C),(2,D). Choose A on the tie, then C, D, B. Each step moves one pointer; total pointer advances equal the output length. At most a+b-1 key comparisons merge nonempty runs of lengths a and b; after one run empties, drain the other without comparing heads.

For eight records, three bottom-up passes merge widths 1, 2, and 4. Every pass writes eight records, so this implementation makes 24 output writes. That is not 24 comparisons: comparisons stop early on some merges. A single reusable buffer avoids repeated allocations. For five records the final short run is handled with min(lo+width,n) boundaries, not discarded.

Common Confusion / Misconceptions​

Recursion does not itself cause the speedup; balanced sizes and linear combine work do. The standard slicing implementation can still have O(n) peak live auxiliary storage under sequential execution, while allocating O(n log n) total slots over its run. Peak storage and cumulative allocation are different metrics. An API that writes back into the input may still allocate a full-sized buffer. Neither quicksort nor mergesort is universally faster in wall-clock time.

How To Use It​

In Lab A, implement bottom-up merging using a second list and swapping source and destination after each width. Compare keys alone, never payloads. State the pass invariant: every run of the current width is sorted and stable. If you add an already-ordered boundary shortcut, explain how it changes work on sorted inputs and preserves the permutation contract.

Check Yourself​

  1. Why must equal keys choose the left run first?
  2. Which operation count is exactly n per full merge pass?
  3. How does the recurrence change if combining takes Theta(n log n)?
  4. What memory does an API's "in-place" wording actually promise?

Mini Drill or Application​

Derive an inversion counter: when a right key is strictly smaller than the left head, add the number of remaining left keys. Explain why equality adds zero. Check [2,4,1,3,5] gives three inversions. Prove that each cross-inversion is counted once, then test against a quadratic oracle on short arrays.

Read This Only If Stuck​

Use CLRS, Skiena, or Sedgewick and Wayne for merge correctness, stable merging, and inversion counting. These links open book indexes; find the named topic in your edition. Use the reading guide for the bounded assignment and worked examples before adding another source.