Merge Sort
Merge sort is a divide-and-conquer algorithm that solves sorting by recursively splitting the problem in half, sorting each half independently, and then me...
Divide, Conquer, and Merge
Merge sort is a divide-and-conquer algorithm that solves sorting by recursively splitting the problem in half, sorting each half independently, and then merging the two sorted halves into a single sorted array. The key insight is that merging two already-sorted arrays into one sorted array can be done in linear time.
The algorithm works as follows. If the array has one or zero elements, it is already sorted and you return immediately. Otherwise, split the array at the midpoint into a left half and a right half. Recursively sort the left half. Recursively sort the right half. Merge the two sorted halves using two pointers, one for each half, advancing the pointer that points to the smaller element at each step.
A worked example: sort the array 38, 27, 43, 3, 9, 82, 10. Split into 38, 27, 43, 3 and 9, 82, 10. Recursively sort each half to get 3, 27, 38, 43 and 9, 10, 82. Merge: compare 3 and 9, take 3. Compare 27 and 9, take 9. Compare 27 and 10, take 10. Compare 27 and 82, take 27. Take 38, then 43, then 82. Result: 3, 9, 10, 27, 38, 43, 82.
Time complexity is O(n log n) in all cases: best, average, and worst. The division creates log n levels of recursion and each level processes all n elements in linear time during the merge phase. Space complexity is O(n) for the temporary arrays used during merging, plus O(log n) for the recursive call stack.
Merge sort is stable because the merge step always takes the left element when left and right elements are equal, preserving original order.
Interview tip: merge sort's guaranteed O(n log n) worst-case performance makes it superior to quick sort in scenarios where predictable performance matters more than average-case speed, such as real-time systems or sorting data that an adversary might have crafted to trigger worst-case behavior in quick sort.
The Merge Operation in Detail
The merge operation is the heart of merge sort and understanding it deeply is essential because the same pattern appears in many other algorithms. Given two sorted arrays A of length p and B of length q, merging them into a single sorted array of length p plus q takes exactly p plus q minus 1 comparisons in the worst case and as few as min(p, q) comparisons in the best case.
Pseudocode for merge: create a result array of size p plus q. Set i to 0 (pointer into A), j to 0 (pointer into B), k to 0 (pointer into result). While i is less than p and j is less than q, if A at i is less than or equal to B at j, copy A at i to result at k and increment i. Otherwise copy B at j to result at k and increment j. Increment k. After the while loop, copy remaining elements from A (if any) or B (if any) to result.
The best case occurs when every element of the smaller array is smaller than every element of the larger array. In that case all min(p, q) elements of the smaller array are consumed first and the remaining elements of the larger array are copied without comparison.
An important optimization for practical implementations: if the last element of the left half is already less than or equal to the first element of the right half, no merging is needed and the two halves are already in order. This optimization makes merge sort adaptive and reduces its time to O(n) on already-sorted input when combined with the bottom-up iterative form.
Bottom-up merge sort avoids recursion entirely by starting with subarrays of size 1 and doubling the subarray size with each pass over the data. This uses O(n) space but O(1) stack space, making it suitable for embedded systems and functional-style implementations.
A worked example of the optimization: the array 1, 2, 3, 4, 5, 6, 7, 8 split into 1, 2, 3, 4 and 5, 6, 7, 8. The last element of the left half (4) is less than the first element of the right half (5), so the merge step copies elements without any comparisons.
Interview tip: describe the best-case merge optimization to show you understand how merge sort can be made adaptive, bridging the gap between its standard O(n log n) guarantee and the O(n) performance achievable on nearly sorted data.
External Merge Sort and Applications
Merge sort is the algorithm of choice for sorting data that does not fit in RAM. When data lives on disk or in a distributed file system, random access is prohibitively expensive and algorithms that rely on it, like quick sort and heap sort, become impractical. Merge sort's sequential access pattern maps directly to the way disk I/O and network transfers work efficiently.
External merge sort works in two phases. In the sort phase, chunks of data that fit in RAM are loaded, sorted in memory using any in-memory sort, and written back to disk as sorted runs. In the merge phase, multiple sorted runs are merged together simultaneously. With k runs and a buffer that can hold b elements, a k-way merge processes all runs in a single pass, requiring only log base k of the total number of initial runs merge passes.
A worked example: you need to sort 10 terabytes of log data on a machine with 10 gigabytes of RAM. You divide the data into 1,000 chunks of 10 gigabytes each, sort each chunk in memory and write it to disk, then merge all 1,000 sorted runs simultaneously using a min-heap to track which run currently holds the smallest element. The min-heap has 1,000 entries, which fits easily in RAM. Each log line is read from disk exactly twice and written exactly twice.
This pattern is used in MapReduce, Apache Spark, PostgreSQL's sort node, and virtually every large-scale data processing system in the world.
Merge sort also underlies the Timsort algorithm used in Python and Java for in-memory sorting. Timsort detects natural runs (already sorted subsequences) in the input and merges them intelligently, achieving O(n) time on already-sorted and nearly sorted data while maintaining O(n log n) worst-case guarantees.
Time complexity: O(n log n) in all cases. Space complexity: O(n) in-memory, O(total data size) on disk during external sort.
Interview tip: mentioning external sort demonstrates that you think about algorithm design beyond the RAM model, which is a key differentiator for senior engineering roles working on data systems.