Merge Sort

Introduction

Merge sort, invented by John von Neumann in 1945, is the canonical example of a divide and conquer sorting algorithm. It consistently achieves O(n log n) time complexity in all cases -- best, average, and worst -- making it one of the most reliable sorting algorithms available.

The algorithm perfectly illustrates the three phases of divide and conquer: it divides the array into two halves, recursively sorts each half, and merges the two sorted halves into a single sorted array. The merge step is the key operation that makes the algorithm work, and understanding it is essential to understanding the divide and conquer paradigm.

Divide, Conquer, Combine

Divide

Split the array into two subarrays of approximately equal size. The dividing point is the middle index: mid = (low + high) / 2. This takes O(1) time.

Conquer

Recursively sort the left subarray (from low to mid) and the right subarray (from mid+1 to high). The base case is a subarray of size 0 or 1, which is already sorted.

Combine

Merge the two sorted subarrays into a single sorted array. This is the most substantive step, requiring O(n) time and O(n) additional space.

In merge sort, all the real work happens in the combine (merge) step. This contrasts with quick sort, where all the real work happens in the divide (partition) step and the combine step is trivial.

Algorithm and Pseudocode

procedure MergeSort(arr, low, high): if low < high: mid = (low + high) / 2 MergeSort(arr, low, mid) // sort left half MergeSort(arr, mid + 1, high) // sort right half Merge(arr, low, mid, high) // merge sorted halves

The recursion creates a binary tree of subproblems. At the top level, we sort the entire array. At the next level, we sort two halves. Then four quarters, and so on, until we reach individual elements. The depth of this tree is log2(n), and at each level, the total work across all merges is O(n).

The Merge Procedure

procedure Merge(arr, low, mid, high): // Create temporary arrays left = arr[low..mid] right = arr[mid+1..high] i = 0, j = 0, k = low // Merge by comparing elements while i < length(left) and j < length(right): if left[i] <= right[j]: arr[k] = left[i] i = i + 1 else: arr[k] = right[j] j = j + 1 k = k + 1 // Copy remaining elements while i < length(left): arr[k] = left[i] i = i + 1 k = k + 1 while j < length(right): arr[k] = right[j] j = j + 1 k = k + 1

The merge procedure uses the fact that both halves are already sorted. It maintains two pointers, one for each half, and repeatedly selects the smaller of the two pointed-to elements. This produces a sorted merged array in O(n) time using O(n) extra space.

Using <= (rather than <) in the comparison ensures stability: equal elements from the left half appear before those from the right half, preserving their original relative order.

Worked Example

Sort the array [38, 27, 43, 3, 9, 82, 10]:

Level 0: [38, 27, 43, 3, 9, 82, 10] / \Level 1: [38, 27, 43, 3] [9, 82, 10] / \ / \Level 2: [38, 27] [43, 3] [9, 82] [10] / \ / \ / \Level 3: [38] [27] [43] [3] [9] [82]Merge back:Level 2: [27, 38] [3, 43] [9, 82] [10]Level 1: [3, 27, 38, 43] [9, 10, 82]Level 0: [3, 9, 10, 27, 38, 43, 82]

At each level, every element participates in exactly one merge operation. With 7 elements and 3 levels (ceil(log2(7)) = 3), the total work is approximately 7 * 3 = 21 comparisons.

Complexity Analysis

Recurrence Relation and Master Theorem

The recurrence for merge sort is:

T(n) = 2T(n/2) + O(n)

Applying the Master theorem: a = 2, b = 2, f(n) = O(n). Since log_b(a) = log_2(2) = 1 and f(n) = O(n^1), we are in Case 2, giving T(n) = O(n log n).

This can also be verified by expansion: there are log2(n) levels, each doing O(n) total work, for O(n log n) overall.

Comparison Count

Merge sort performs between n*ceil(log2(n)) - 2^ceil(log2(n)) + 1 (best case) and n*ceil(log2(n)) - 2^ceil(log2(n)) + n (worst case) comparisons. For n = 1000, this is between approximately 8977 and 9976 comparisons.

The information-theoretic lower bound for comparison-based sorting is ceil(log2(n!)) comparisons, which is approximately n*log2(n) - n*log2(e). Merge sort is within a small constant factor of this optimal bound.

Variants

Bottom-Up Merge Sort

Instead of recursing top-down, bottom-up merge sort iteratively merges subarrays of increasing size: first pairs of single elements, then pairs of pairs, and so on. This avoids recursion overhead and is often used in practice.

Natural Merge Sort

This variant identifies already-sorted runs in the input and merges them. For nearly-sorted data, it can approach O(n) performance. Python's Timsort is based on this idea.

In-Place Merge Sort

Several algorithms achieve O(n log n) sorting with O(1) extra space by performing merges in-place, but these are significantly more complex and have larger constant factors.

Parallel Merge Sort

Merge sort is naturally parallelizable: the two recursive calls are independent and can run simultaneously. With p processors, the depth is O(log^2 n) using a parallel merge procedure.

Comparison with Other Sorts

Merge sort is preferred when stability is required or when worst-case guarantees matter (e.g., in real-time systems). Quick sort is preferred when average-case performance and low memory usage are more important.

References

• von Neumann, J. "First Draft of a Report on the EDVAC." 1945.
• Knuth, D. E. "The Art of Computer Programming, Volume 3: Sorting and Searching." Addison-Wesley, 1973.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. "Introduction to Algorithms." MIT Press, Chapter 2, 2009.
• Sedgewick, R. and Wayne, K. "Algorithms." Addison-Wesley, 4th edition, 2011.
• Peters, T. "Timsort - Description of the Algorithm." Python Dev Documentation, 2002.