Merge Sort

Introduction

Merge sort is a divide-and-conquer sorting algorithm that was invented by John von Neumann in 1945. It works by recursively dividing the array into two halves, sorting each half, and then merging the two sorted halves back together. The key operation is the merge step, which combines two sorted sequences into a single sorted sequence in linear time.

Merge sort is one of the most important sorting algorithms in computer science. It guarantees O(n log n) time complexity in all cases -- best, average, and worst -- making it more predictable than quicksort. It is also a stable sort, meaning that elements with equal keys retain their original relative order. These properties make it the algorithm of choice in many standard library implementations.

The primary drawback of merge sort is that it requires O(n) additional memory for the merge operation, which can be significant for very large datasets. However, this trade-off is often acceptable given its consistent performance and stability guarantees.

"Merge sort is the algorithm of choice for sorting linked lists. It requires no random access to data, only sequential access, and it guarantees O(n log n) performance." -- Robert Sedgewick, Algorithms

How It Works

Divide-and-Conquer Strategy

Merge sort follows the classic divide-and-conquer paradigm, consisting of three steps:

1. Divide: Split the array into two halves at the midpoint.
2. Conquer: Recursively sort each half. The base case is an array of one element, which is trivially sorted.
3. Combine: Merge the two sorted halves into a single sorted array by comparing elements from each half and placing them in order.

The Merge Operation

The merge step is the heart of the algorithm. Given two sorted subarrays, it produces a single sorted array by maintaining a pointer into each subarray and repeatedly choosing the smaller of the two pointed-to elements. When one subarray is exhausted, the remaining elements of the other are appended directly.

This merge operation runs in O(n) time, where n is the total number of elements across both subarrays, because each element is compared and placed exactly once.

Algorithm and Pseudocode

Recursive Merge Sort

procedure mergeSort(A : array, left : int, right : int) if left < right then mid := (left + right) / 2 mergeSort(A, left, mid) // Sort left half mergeSort(A, mid + 1, right) // Sort right half merge(A, left, mid, right) // Merge sorted halves end ifend procedure

Merge Procedure

procedure merge(A : array, left : int, mid : int, right : int) // Create temporary arrays L := A[left..mid] // Copy left half R := A[mid+1..right] // Copy right half i := 0 // Index into L j := 0 // Index into R k := left // Index into A // Merge L and R back into A while i < length(L) and j < length(R) do if L[i] <= R[j] then A[k] := L[i] i := i + 1 else A[k] := R[j] j := j + 1 end if k := k + 1 end while // Copy remaining elements of L, if any while i < length(L) do A[k] := L[i] i := i + 1 k := k + 1 end while // Copy remaining elements of R, if any while j < length(R) do A[k] := R[j] j := j + 1 k := k + 1 end whileend procedure

Note the use of <= in the comparison L[i] <= R[j]. This ensures stability: when two elements are equal, the one from the left half (which appeared earlier in the original array) is placed first.

Time and Space Complexity

Space Complexity: O(n). The standard implementation requires O(n) auxiliary space for the temporary arrays used during merging. The recursion stack adds O(log n) space, but this is dominated by the merge buffer.

Stability: Merge sort is stable when implemented correctly (using <= rather than < when comparing elements from the left and right halves).

Recurrence Relation

The time complexity of merge sort is described by the recurrence:

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

By the Master Theorem (case 2), this resolves to T(n) = O(n log n).

Worked Example

Sort the array [38, 27, 43, 3, 9, 82, 10] using merge sort.

Division Phase

Merge Phase

Detailed Final Merge

Merging [3, 27, 38, 43] and [9, 10, 82]:

• Compare 3 and 9: take 3. Result: [3]
• Compare 27 and 9: take 9. Result: [3, 9]
• Compare 27 and 10: take 10. Result: [3, 9, 10]
• Compare 27 and 82: take 27. Result: [3, 9, 10, 27]
• Compare 38 and 82: take 38. Result: [3, 9, 10, 27, 38]
• Compare 43 and 82: take 43. Result: [3, 9, 10, 27, 38, 43]
• Right exhausted: append 82. Result: [3, 9, 10, 27, 38, 43, 82]

Advantages and Disadvantages

Advantages

• Guaranteed O(n log n): No worst-case degradation. Performance is consistent regardless of input distribution.
• Stable: Preserves the relative order of elements with equal keys, which is essential for multi-key sorting.
• Parallelizable: The independent recursive calls on the two halves can be executed in parallel on multi-core systems.
• Excellent for linked lists: Can sort linked lists in O(n log n) time with only O(log n) extra space (for recursion), since merging linked lists requires no additional buffer.
• Predictable: Consistent running time makes it suitable for real-time or latency-sensitive applications.

Disadvantages

• O(n) extra space: Requires auxiliary arrays for merging, which doubles memory usage for array-based implementations.
• Not in-place: Unlike quicksort and heapsort, standard merge sort cannot sort within the original array alone.
• Overhead for small arrays: The recursive function calls and array copying add overhead that makes it slower than insertion sort for small datasets.
• Cache performance: The non-sequential memory access patterns during merging can lead to more cache misses than quicksort.

Comparison with Other Algorithms

Merge Sort vs. Quick Sort: Quicksort is typically faster in practice due to better cache locality and lower constant factors, but its O(n^2) worst case is a serious concern for adversarial inputs. Merge sort's guaranteed O(n log n) and stability make it preferable when worst-case guarantees or stability are required.

Merge Sort vs. Heap Sort: Both guarantee O(n log n) time. Heap sort uses O(1) space but is not stable and has worse cache performance. Merge sort is stable and often faster in practice but requires O(n) extra space.

Merge Sort vs. Timsort: Timsort is a hybrid algorithm that combines merge sort with insertion sort and takes advantage of existing runs (sorted subsequences) in the data. It is used as the default sort in Python and Java. Timsort achieves O(n) on already-sorted data while maintaining merge sort's O(n log n) worst case.

Implementation Notes

Bottom-Up Merge Sort

An iterative variant that avoids recursion. It starts by treating each element as a sorted subarray of size 1, then repeatedly merges adjacent subarrays of increasing size (1, 2, 4, 8, ...) until the entire array is sorted.

procedure bottomUpMergeSort(A : array) n := length(A) width := 1 while width < n do for i := 0 to n - 1 step 2 * width do left := i mid := min(i + width - 1, n - 1) right := min(i + 2 * width - 1, n - 1) merge(A, left, mid, right) end for width := width * 2 end whileend procedure

Natural Merge Sort

A variant that identifies naturally occurring sorted runs in the input and merges them, rather than always splitting at the midpoint. This makes it adaptive: it runs in O(n) time on already-sorted data. Timsort is based on this idea.

In-Place Merge Sort

It is possible to implement merge sort in-place using O(1) extra space, but such implementations are complex and have larger constant factors that make them slower in practice. The standard O(n) space version is preferred in nearly all practical applications.

Optimization: Use Insertion Sort for Small Subarrays

Most practical implementations switch to insertion sort when the subarray size falls below a threshold (typically 7-50 elements). This avoids the overhead of recursive calls and array copying for small subarrays where insertion sort's simplicity and cache friendliness provide better performance.

Applications

• External sorting: Merge sort is the foundation of external sorting algorithms used when data is too large to fit in memory. Data is divided into chunks that fit in RAM, each chunk is sorted, and then the sorted chunks are merged from disk.
• Linked list sorting: The algorithm of choice for sorting linked lists because the merge operation can be performed without additional memory allocation.
• Standard library implementations: Python's sorted() and Java's Arrays.sort() for objects use Timsort, which is derived from merge sort.
• Counting inversions: A modified merge sort can count the number of inversions in an array in O(n log n) time, which is useful in ranking and statistics.
• Parallel processing: The independent recursive subproblems make merge sort highly amenable to parallel execution on multi-core processors and distributed systems.
• Stable sorting requirement: Any application where the relative order of equal elements must be preserved benefits from merge sort's stability.

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to Algorithms, 4th Edition. MIT Press, 2022. Chapter 2: Getting Started (Merge Sort), Chapter 4: Divide-and-Conquer.
• Knuth, D. E. The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd Edition. Addison-Wesley, 1998. Section 5.2.4: Sorting by Merging.
• Sedgewick, R. and Wayne, K. Algorithms, 4th Edition. Addison-Wesley, 2011. Section 2.2: Mergesort.
• von Neumann, J. "First Draft of a Report on the EDVAC." Moore School of Electrical Engineering, University of Pennsylvania, 1945.