Merge sort works by repeatedly splitting an array in half until each piece contains just one element, then combining those pieces back together in sorted order. It’s one of the most reliable sorting algorithms in computer science, running in O(n log n) time in every case, whether the input is already sorted, completely reversed, or random. That predictability is why variations of merge sort power the default sorting functions in Python, Java, and many other languages.
The Three-Step Process
Merge sort follows a strategy called “divide and conquer,” which breaks down into three repeating steps:
- Divide: Split the array into two halves. If the array has an odd number of elements, one half gets one extra element.
- Recurse: Apply the same splitting process to each half, and keep splitting until every piece is a single element. A single element is already “sorted” by definition, so that’s where the splitting stops.
- Merge: Combine the single-element pieces back together into sorted pairs, then combine those pairs into sorted groups of four, and so on, until you have one fully sorted array.
Think of it like organizing a shuffled deck of cards. You split the deck in half, split each half in half again, and keep going until you’re holding individual cards. Then you start combining them: pick the smaller of two cards to go first, then the smaller of the next two, building up sorted groups that get larger until the whole deck is in order.
How the Merge Step Works
The merge is where the actual sorting happens. You start with two sorted subarrays and need to combine them into one sorted result. The process uses a simple comparison: look at the first (smallest) element of each subarray, pick whichever is smaller, and place it into the output. Then move forward in whichever subarray you picked from, and repeat.
For example, say you’re merging [2, 5, 8] and [1, 3, 9]. Compare 2 and 1. Since 1 is smaller, it goes first. Now compare 2 and 3. Since 2 is smaller, it goes next. Compare 5 and 3, pick 3. Compare 5 and 9, pick 5. Compare 8 and 9, pick 8. Only 9 is left, so it goes at the end. Result: [1, 2, 3, 5, 8, 9].
This merge operation requires a temporary auxiliary array to hold the results before copying them back. That extra memory is the main tradeoff of merge sort compared to algorithms like quicksort that sort elements in place.
A Walkthrough With Numbers
Start with the array [38, 27, 43, 3, 9, 82, 10]. Here’s what happens:
First, split into [38, 27, 43, 3] and [9, 82, 10]. Split again into [38, 27], [43, 3], [9, 82], and [10]. Split once more: [38], [27], [43], [3], [9], [82], [10]. Every piece is now a single element.
Now merge back up. Merge [38] and [27] into [27, 38]. Merge [43] and [3] into [3, 43]. Merge [9] and [82] into [9, 82]. The [10] has no partner at this level, so it waits. Next level: merge [27, 38] and [3, 43] into [3, 27, 38, 43]. Merge [9, 82] and [10] into [9, 10, 82]. Final merge: [3, 27, 38, 43] and [9, 10, 82] become [3, 9, 10, 27, 38, 43, 82].
Why It Always Runs in O(n log n)
Merge sort’s performance doesn’t depend on how the input data is arranged. The reason comes down to two observations. First, each level of the splitting process cuts the array size in half. Starting with n elements and halving repeatedly until you reach single elements takes log₂ n levels. Second, at every level, the merge step touches each of the n elements exactly once, doing a constant amount of work per element.
The total work is n elements multiplied by log₂ n levels, giving O(n log n). This holds whether the data starts sorted, reversed, or in random order, because the algorithm always splits and merges the same way regardless of element order. That consistency is a major advantage over quicksort, which runs in O(n log n) on average but can degrade to O(n²) in the worst case.
The Memory Tradeoff
The standard recursive (top-down) version of merge sort needs O(n log n) space because it creates temporary arrays during each level of recursion. A bottom-up iterative version reduces this to O(n) by reusing a single auxiliary array, which is a meaningful improvement for large datasets.
Either way, merge sort uses more memory than quicksort, which operates in O(1) extra space. This is the core tradeoff: merge sort guarantees consistent speed at the cost of extra memory, while quicksort saves memory but risks slower performance on unlucky inputs.
Top-Down vs. Bottom-Up Approaches
The version described above is “top-down” merge sort. It starts with the full array, recursively splits it in half, and merges on the way back up. This is the version most people learn first because the recursive logic maps naturally to the divide-and-conquer concept.
“Bottom-up” merge sort skips the recursive splitting entirely. Instead, it starts by treating every element as its own sorted run of length one. It merges adjacent pairs into sorted runs of length two, then merges those into runs of length four, then eight, and so on until the entire array is sorted. The time complexity is identical at O(n log n), but the bottom-up approach avoids the overhead of recursive function calls and uses only O(n) auxiliary space. For this reason, bottom-up merge sort is often preferred in production implementations.
Stability: Keeping Equal Elements in Order
Merge sort is a stable sorting algorithm, meaning elements with equal values keep their original relative order after sorting. If you’re sorting a list of students by grade and two students both have a B+, merge sort guarantees they’ll appear in the same order they were in before the sort.
Stability comes from the merge step. When comparing two equal elements, the algorithm always picks the one from the left subarray first. This preserves original ordering because left-subarray elements always came before right-subarray elements in the original array. Stability matters in practice when you’re sorting by multiple criteria. You can sort by last name first, then by grade, and the alphabetical order within each grade group is preserved.
Where Merge Sort Is Used Today
Most modern programming languages don’t use pure merge sort for their built-in sorting functions, but they use algorithms heavily based on it. Timsort, a hybrid of merge sort and insertion sort, was developed by Tim Peters in 2002 for Python and remained Python’s standard sort through version 3.11 (when it was replaced by Powersort, another merge-based algorithm). Java SE 7 adopted Timsort for sorting objects, and it’s also used in Android, Swift, and the V8 JavaScript engine.
These hybrid algorithms exploit the fact that real-world data often contains partially sorted “runs.” They detect existing order in the input and use insertion sort for small segments, falling back to merge sort’s merging strategy for combining larger pieces. The result is an algorithm that matches merge sort’s O(n log n) worst case while performing even faster on data that already has some structure.
Merge Sort and Parallel Computing
The divide-and-conquer structure of merge sort makes it naturally suited for parallel processing. Once you split the array into two halves, each half can be sorted independently on a separate processor. The simplest parallel version just runs the recursive calls in parallel, but the merge step remains a bottleneck because it’s inherently sequential: you need to compare elements one at a time.
More advanced versions also parallelize the merge operation itself, using binary search to figure out where elements from one subarray should be inserted into the other. On a machine with unlimited processors, this can reduce the merge cost from linear to logarithmic. In practice, research on parallel merge sort implementations shows that combining parallel recursion with a parallel merge gives better speedup than parallelizing the recursion alone, with the best results achieved in shared-memory environments where processors can access the same data without network overhead.