In our journey through algorithms, we have seen recursion as both a programming style and a reflection of induction in mathematics. Today we turn to one of the most elegant children of recursion: MergeSort, the sorting algorithm that embodies the spirit of divide and conquer.
The Problem: Sorting a Sequence
Given an array $A[p..r]$, the goal is simple: rearrange its elements in ascending order.
Naïve strategies, such as insertion sort, achieve this with quadratic cost in the worst case, $\Theta(n^2)$. For large $n$, this becomes prohibitive.
MergeSort proposes something more refined: split, sort, and merge.
The Algorithm
In pseudocode:
MergeSort(A, p, r):
if p < r:
q = ⌊(p + r)/2⌋
MergeSort(A, p, q)
MergeSort(A, q+1, r)
Merge(A, p, q, r)
- Divide: Compute the midpoint $q$.
- Conquer: Recursively sort $A[p..q]$ and $A[q+1..r]$.
- Combine: Merge the two sorted halves into one sorted sequence.
Like a symphony divided into movements, each part is simple, but the combination yields harmony.
The Merge Procedure
The key is the subroutine Merge, which takes two sorted halves and produces a sorted whole.
Here is a clean version in Python:
def merge(A, p, q, r):
L = A[p:q+1]
R = A[q+1:r+1]
i, j, k = 0, 0, p
while i < len(L) and j < len(R):
if L[i] <= R[j]:
A[k] = L[i]
i += 1
else:
A[k] = R[j]
j += 1
k += 1
while i < len(L):
A[k] = L[i]
i += 1
k += 1
while j < len(R):
A[k] = R[j]
j += 1
k += 1
This procedure is linear: it examines each of the $n = r-p+1$ elements once, performing $\Theta(n)$ work.
The Recurrence for $T(n)$
Let $T(n)$ denote the time to sort $n$ elements.
- Dividing costs constant time.
- Recursively, we sort two halves of size about $n/2$.
- Merging costs $\Theta(n)$.
Thus,
\[T(n) = 2T\!\left(\frac{n}{2}\right) + \Theta(n).\]For powers of two, the recurrence unfolds as:
\[T(n) = 2T\!\left(\frac{n}{2}\right) + cn \\ = 4T\!\left(\frac{n}{4}\right) + 2cn \\ = \dots \\ = 2^k T\!\left(\frac{n}{2^k}\right) + kcn.\]When $n/2^k = 1$, we have $k = \log_2 n$ and $T(1) = a$.
So,
MergeSort is linearithmic. Unlike insertion sort, which drowns in quadratic growth, MergeSort glides smoothly even for massive input sizes.
Divide and Conquer as Philosophy
Why is this method powerful? Think of a large musical composition: you don’t play it in a single breath. It is broken into movements, rehearsed in parts, and finally assembled into a masterpiece. MergeSort reflects this artistic principle.
The act of splitting a problem into smaller, tractable problems and then merging solutions appears in physics (particle interactions forming systems), in literature (chapters forming a novel), and even in our own cognition (breaking challenges into steps).
Comparing MergeSort with Other Algorithms
From the CT234 lectures on sorting:
- Bubble, Selection, Insertion Sorts: $\Theta(n^2)$ worst case.
- HeapSort, QuickSort, MergeSort: $\Theta(n \log n)$ in the average or worst case.
- Radix and Counting Sorts: Can achieve $\Theta(n)$ but under stricter assumptions (keys with limited range).
MergeSort stands out because its performance guarantee is universal: all inputs cost about the same. There is no “bad pivot” like in QuickSort, nor fragile assumptions like in Counting Sort.
An Iterative View: Bottom-Up MergeSort
Recursion is not mandatory. MergeSort can be written iteratively: start merging pairs of length 1, then length 2, then length 4, doubling each round.
This bottom-up MergeSort is equivalent in complexity, and often used in external sorting, where disk access dominates.
Exercises for the Reader
- Prove formally that the number of comparisons in the merge step is exactly $n-1$ for $n$ elements.
- Show by induction that the recurrence $T(n) = 2T(n/2) + cn$ solves to $T(n) = O(n \log n)$.
- Implement both top-down and bottom-up MergeSort in Python. Compare them on random arrays of size $10^6$.
- Which one is faster in practice? Why?
- Imagine you have four sorted playlists of songs. Describe how to merge them efficiently into a single sorted playlist. What is the time complexity?
- Advanced: adapt MergeSort to count the number of inversions in an array (pairs $(i,j)$ such that $i<j$ and $A[i]>A[j]$). What is the complexity?
Beyond the Algorithm
MergeSort is not just a sorting routine. It is an expression of a deeper truth: order is born from synthesis, not from brute force. By dividing, we conquer complexity. By merging, we reassemble meaning.
From arranging notes into symphonies to aligning galaxies into clusters, nature itself seems to prefer MergeSort over brute insertion.