☕ Buy me a coffee — $3

Merge Sort

Overview

Merge Sort is a divide-and-conquer sorting algorithm that divides the array into two halves, sorts them recursively, and then merges the sorted halves. It is one of the most efficient sorting algorithms with a guaranteed O(n log n) time complexity in all cases.

Merge Sort is stable, meaning it preserves the relative order of equal elements, and it's particularly well-suited for sorting linked lists and external sorting (sorting data too large to fit in memory).

It is one of the most historically important algorithms in computing. The core idea, solve a large problem by recursively splitting it into independent subproblems, then combining their solutions, is essentially the founding statement of the divide-and-conquer paradigm, and merge sort is the first non-trivial algorithm ever proven to run in optimal O(n log n) time. It underpins the sorting subsystems of major databases, drives the shuffle phase of every MapReduce implementation, and is the direct ancestor of Timsort, the algorithm Python and Java use for their default sort.

Historical Significance

Merge sort was designed by John von Neumann in 1945, in a report titled "First Draft of a Report on the EDVAC" that also introduced the stored-program computer architecture that all modern computers still use. Sorting was one of the first non-trivial problems von Neumann considered when working out what a general-purpose computer could actually be programmed to do, and merge sort was the algorithm he chose, because the merge step maps naturally onto sequential magnetic tape, the storage medium of the day.

That tape-driven origin is worth understanding, because it explains why merge sort has the shape it does. On a tape, you can read forward efficiently but random access is prohibitively slow, the tape has to physically wind past the intervening data. Merging two sorted tapes into a third is a purely sequential operation, one read from each input tape at a time and one write to the output. This is perfect for tape hardware, and it is why merge sort is still the algorithm of choice for external sorting: sorting data too large to fit in memory. Modern databases sorting a terabyte of data on spinning disks or SSDs use exactly the same pattern von Neumann designed, split into chunks that fit in memory, sort each chunk in memory, then merge the sorted chunks in a k-way merge back onto disk. The shape of the algorithm has not changed in 80 years.

The formal analysis showing merge sort achieves the theoretical lower bound for comparison-based sorting, the information-theoretic result that any comparison sort must perform at least Ω(n log n) comparisons, was worked out over the following two decades. This makes merge sort not just historically important but also asymptotically optimal in the comparison model. You cannot do better in the general case; you can only trade constants, adapt to structure in the input, or move to a different computational model (like radix sort, which is not comparison-based).

How It Works

The algorithm follows these steps:

  1. Divide: Split the array into two halves
  2. Conquer: Recursively sort both halves
  3. Combine: Merge the two sorted halves into a single sorted array

The base case occurs when the array has 0 or 1 element, which is already sorted. The merge step combines two sorted arrays by comparing elements from both arrays and placing them in order.

Algorithm


MergeSort(arr):
    if length of arr <= 1:
        return arr
    
    mid = length of arr / 2
    left = MergeSort(first half of arr)
    right = MergeSort(second half of arr)
    
    return Merge(left, right)

Merge(left, right):
    result = []
    i = 0, j = 0
    
    while i < length of left and j < length of right:
        if left[i] <= right[j]:
            append left[i] to result
            i = i + 1
        else:
            append right[j] to result
            j = j + 1
    
    append remaining elements from left to result
    append remaining elements from right to result
    
    return result

Implementation


def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Complexity Analysis

  • Time Complexity: O(n log n) in all cases (best, average, and worst)
    • The divide step takes O(1)
    • Each recursive call processes half the array: O(log n) levels
    • Merging two arrays of size n/2 takes O(n) time
    • Total: O(n log n)
  • Space Complexity: O(n) - requires additional space for the temporary arrays during merging

Characteristics

  • Stable: Yes - maintains relative order of equal elements
  • In-place: No, requires O(n) auxiliary space for the merge (plus O(log n) recursion stack). In-place merge sort variants exist, such as block merge sort / WikiSort, achieving O(1) space and O(n log n) time, but with large constants. On linked lists merge sort genuinely needs only O(1) extra space, since merging is just pointer rewiring.
  • Adaptive: No, classic merge sort performs the same operations regardless of input. Natural merge sort, which detects existing sorted runs, is adaptive and reaches O(n) on sorted input; that idea is the basis of Tim Sort.
  • Online: No - requires the entire array to be present

Merge Sort on Linked Lists

Merge sort has one property that no other O(n log n) sort can match: on linked lists it runs in O(1) auxiliary space. This is worth understanding because it changes when merge sort is the right choice.

On arrays, the merge step needs an auxiliary buffer because you have to read from the two halves and write to a third location without corrupting either input. On a linked list, merging is not a data-copy operation, it is a pointer rewiring operation. You walk the two sorted lists in parallel, and at each step you re-point one node's next pointer to weave the smaller element into the merged list. No new nodes are allocated, no values are copied, and the result is a merged sorted list using exactly the same memory the inputs occupied.

This gives merge sort a unique position for linked-list sorting: it is asymptotically optimal (O(n log n)), stable, and truly in-place. Quicksort on linked lists is awkward because random access is expensive; heap sort requires a heap structure that linked lists cannot provide without O(n) auxiliary space. If your data is already in linked-list form, as it often is in Lisp-descended languages, in Java's LinkedList, or in low-level systems code with intrusive list structures, merge sort is the correct sort.

The base case for a linked-list merge sort is the empty or single-node list, and the "split" step is typically implemented with the two-pointer "slow and fast" technique, advance one pointer at each step, another at every second step, and when the fast pointer reaches the end the slow pointer is at the midpoint. Total work per level is O(n), levels are O(log n), and no allocations happen at any point.

Parallel and External Merge Sort

The divide-and-conquer structure that makes merge sort work also makes it one of the easiest sorts to parallelise. The two recursive calls on the left and right halves are completely independent, no shared state, no ordering constraint, so a work-stealing scheduler can hand them to different cores and get linear speedup for the recursive phase. The merge step itself parallelises less trivially but has known techniques: parallel merge uses binary search to find the median of the merged output and splits both input arrays around it, giving O(log² n) span per merge level. Rust's rayon library, Java's Arrays.parallelSort, and C++'s parallel STL algorithms all use variants of parallel merge sort for exactly these properties.

External merge sort handles data too large to fit in RAM. The algorithm is the same in spirit: split the input into memory-sized chunks, sort each chunk in memory (usually with quicksort or Timsort, which are faster in RAM), write the sorted chunks to disk as "runs," then merge the runs in a k-way merge back to a single output. The k-way merge uses a min-heap over the current head of each run, extract the smallest, advance that run, and repeat. If you have m runs and can hold r of them in memory at once, the merge takes ⌈logr m⌉ passes over the data. Database systems, big-data frameworks like Hadoop and Spark, and Unix's sort command all use variants of this scheme, sometimes with elaborate optimisations for compression, tape layout, or distributed shuffling, but always with von Neumann's original algorithm at the core.

Variants Worth Knowing

Natural Merge Sort

Instead of splitting the array in half regardless of structure, natural merge sort scans the input for existing sorted "runs" and merges those. On uniformly random data this makes no difference, the expected run length is small, but on real-world data, which often has long sorted subsequences, it is dramatically faster. On a fully-sorted input, natural merge sort detects a single run of length n and terminates in O(n). This adaptivity is the direct ancestor of Timsort, which is essentially natural merge sort with a merge stack invariant and a galloping merge routine bolted on.

Bottom-Up Merge Sort

Eliminates recursion by starting with pairs of adjacent single-element "runs" and merging them into runs of length 2, then length 4, and so on until the whole array is one run. The total work is identical to top-down merge sort, and the implementation is often simpler and faster in practice because it avoids the function-call overhead of recursion. Java's Arrays.sort for object arrays uses a bottom-up variant.

In-Place Merge Sort

Achieving O(1) auxiliary space on an array-based merge sort is a hard problem that was considered impossible for decades. Katajainen, Pasanen and Teuhola showed in 1996 that it is possible with a "block merge" technique that swaps blocks of elements between the two inputs and uses the merged region itself as scratch space, achieving O(n log n) time with O(1) extra memory. The algorithm is beautiful but has large constant factors and complicated code; the modern implementation is called WikiSort. In practice, if you need in-place sorting you usually reach for heap sort or introsort instead, the constant-factor cost of in-place merge sort's clever block manipulation is significant.

Multi-Way Merge Sort

Instead of merging two runs at a time, merge k runs simultaneously using a min-heap. This is the standard implementation for external merge sort because it reduces the number of passes over the (slow) external storage from log2 m to logk m. Modern database engines choose k based on available memory and expected I/O bandwidth.

Common Misconceptions

  • "Merge sort needs O(n) extra space." True for arrays, false for linked lists. On a linked list, merging is pointer rewiring and needs O(1) space. Many people state the array-based space complexity as an inherent property of the algorithm, it is a property of the array representation.
  • "You need to allocate the merge buffer at every level." No, allocate one buffer of size n at the top of the sort and reuse it at every recursive level. Naive implementations that allocate a fresh buffer per merge call are quadratic in memory churn, which is one reason merge sort is sometimes perceived as slower than it actually is.
  • "Merge sort is always stable." Only if the merge step breaks ties in favour of the left input (if left[i] <= right[j]). A merge that writes the right element first on equality is not stable. This is the same subtlety as with bubble sort: stability depends on how you write the comparison.
  • "Merge sort is slower than quicksort in practice." On uniformly random integer arrays that fit in cache, yes. On real data, or when stability is needed, or on arrays that do not fit in cache, merge sort is often competitive or faster. Timsort, a natural merge sort with clever heuristics, is the default sort in Python and Java precisely because it beats quicksort on most workloads people actually run.

When to Use Merge Sort

Merge sort is one of the most versatile sorting algorithms in the toolkit. Choose it when:

  • You need a guaranteed O(n log n) worst case. Quicksort has O(n²) worst case with pathological input; merge sort's guarantee is unconditional. In systems where inputs might be adversarial, a web-facing service sorting user data, for example, the worst-case guarantee matters.
  • You need stability. Sorting by one field of a compound record while preserving a previously-established secondary order requires a stable sort. Merge sort is stable; quicksort and heapsort are not.
  • You are sorting a linked list. On linked lists, merge sort is O(n log n) time and O(1) space, and no other sort achieves both. If your data is naturally a linked list, this is the correct sort.
  • You are sorting more data than fits in memory. External merge sort is the universally-used technique for sorting terabyte-scale data across disk or across a cluster. Every major database, every distributed data processing framework, and Unix's sort command all use it.
  • You want easy parallelism. The independent recursive halves make merge sort one of the easiest sorts to parallelise, and it is the algorithm used by Java's parallelSort and by many multi-threaded sort libraries.

Prefer quicksort when memory is very tight and cache locality matters more than worst-case guarantees. Prefer Timsort for general-purpose sorting on real-world data with structure. Prefer heap sort when you need worst-case O(n log n) with strict O(1) space on arrays.

Example

Sorting [38, 27, 43, 3, 9, 82, 10]: 

Divide:
[38, 27, 43, 3, 9, 82, 10]
[38, 27, 43] [3, 9, 82, 10]
[38] [27, 43] [3, 9] [82, 10]
[38] [27] [43] [3] [9] [82] [10]

Merge:
[38] [27, 43] [3, 9] [10, 82]
[27, 38, 43] [3, 9, 10, 82]
[3, 9, 10, 27, 38, 43, 82]

Related Algorithms

Explore other sorting algorithms: