Merge Sort

Merge sort is a sorting algorithm that orders a sequence by sorting smaller parts and then merging them. It is a classic example of divide and conquer: divide the input into two parts, sort each part, and combine the results. Standard array implementations take $\Theta(n\log n)$ time and $\Theta(n)$ auxiliary space, assuming constant-time comparisons and element movements. Merge sort can preserve the original order of equal-key elements, making it a stable sorting method. (algs4.cs.princeton.edu)

Principle and merging operation

The central operation is merging: combining two already sorted sequences into a single sorted sequence containing all their elements. Keep a position at the beginning of each sequence, compare the two current elements, and output the smaller one. Advance the position in the sequence from which that element was taken. When one sequence is exhausted, append the remaining elements of the other. (xlinux.nist.gov)

For example:

Left:    [2, 5, 8]
Right:   [1, 5, 9]
Merged:  [1, 2, 5, 5, 8, 9]

At every step, the smallest remaining element must be at the current position of one of the two sorted inputs. Consequently, selecting the smaller current element preserves the order of the output. This is the essential loop invariant behind the merge procedure. For inputs of lengths $p$ and $q$, merging takes $\Theta(p+q)$ time when every element is written to the result, and requires at most $p+q-1$ key comparisons if both inputs are nonempty. (algs4.cs.princeton.edu)

Top-down algorithm

The top-down version uses recursion. An empty sequence or a sequence containing one element is already sorted. A longer sequence is split into two approximately equal parts, each is sorted recursively, and the results are merged. The parts need not have identical lengths, so the algorithm does not require the input size to be a power of two. (algs4.cs.princeton.edu)

The following pseudocode uses half-open intervals: A[lo:hi] includes lo but excludes hi. It allocates one auxiliary array and reuses it throughout the recursion.

MERGE_SORT(A):
    B = new array of length length(A)
    SORT_RANGE(A, B, 0, length(A))

SORT_RANGE(A, B, lo, hi):
    if hi - lo <= 1:
        return

    mid = lo + floor((hi - lo) / 2)
    SORT_RANGE(A, B, lo, mid)
    SORT_RANGE(A, B, mid, hi)
    MERGE(A, B, lo, mid, hi)

MERGE(A, B, lo, mid, hi):
    copy A[lo:hi] into B[lo:hi]
    i = lo
    j = mid

    for k = lo to hi - 1:
        if i == mid:
            A[k] = B[j]
            j = j + 1
        else if j == hi:
            A[k] = B[i]
            i = i + 1
        else if B[j] < B[i]:
            A[k] = B[j]
            j = j + 1
        else:
            A[k] = B[i]
            i = i + 1

This formulation follows the standard auxiliary-array approach. Copying the input interval before merging prevents newly written output from overwriting elements that have not yet been processed. Choosing the left element when the keys are equal preserves stability. (algs4.cs.princeton.edu)

Correctness and stability

Correctness follows by mathematical induction on the sequence length. Sequences of length zero or one satisfy the sorting requirement. For a longer sequence, assume the recursive calls correctly sort both smaller parts. Merging then produces a sorted sequence containing precisely the elements of those parts, establishing the result for the original sequence. (arxiv.org)

A stable sort preserves the relative order of records with equal keys. Consider records sorted only by their numeric field:

Input:   [(3, a), (1, b), (3, c), (2, d)]
Output:  [(1, b), (2, d), (3, a), (3, c)]

The two records keyed by 3 retain their original order. In merge sort, this property requires both stable processing within the parts and an appropriate rule for ties during merging. With contiguous input parts, taking the left-hand element first on equality maintains the original order across the boundary. Stability is therefore a property of the implementation, not an automatic consequence of using any merge operation. (algs4.cs.princeton.edu)

Time and space complexity

For balanced splitting and linear-time merging, the recurrence relation for running time is

with constant-time base cases. There are $\Theta(\log n)$ levels, and each complete merging level processes $\Theta(n)$ elements. Thus the ordinary implementation has $\Theta(n\log n)$ time complexity in its best, average, and worst cases. These bounds assume that comparisons and element copies take constant time. (cs.umd.edu)

For standard top-down merge sort on $n=2^k$ elements, the worst-case number of comparisons is

This follows by adding the maximum $m-1$ comparisons for each merge of $m$ elements over all levels. (cs.umd.edu)

The usual array implementation has the following space complexity:

These figures describe peak simultaneously occupied memory, not the total volume of allocations or element movements over the entire execution. Reusing one buffer avoids allocating a separate full-size buffer at every recursive call. (algs4.cs.princeton.edu)

Merge sort is asymptotically optimal in the comparison model. Distinguishing all possible orders of $n$ distinct elements requires at least $\lceil\log_2(n!)\rceil=\Omega(n\log n)$ comparisons in the worst case. This lower bound concerns comparison-based sorting; it does not apply unchanged to algorithms that exploit restricted key representations. The symbols $O$, $\Omega$, and $\Theta$ describe asymptotic growth and are part of asymptotic notation. (algs4.cs.princeton.edu)

Main variants

Bottom-up merge sort

Bottom-up merge sort replaces recursive subdivision with successive passes. It first merges adjacent one-element runs, then runs of length two, then four, and so on until the entire input forms one sorted run. A final run may be shorter than the nominal run length. This version retains the standard $\Theta(n\log n)$ time bound and linear array buffer, while avoiding a recursive call stack. (algs4.cs.princeton.edu)

Natural merge sort

Natural merge sort begins with ordered subsequences already present in the input rather than treating every element as an individual run. Its performance depends on how many runs exist and how the algorithm schedules their merges. Merge-based adaptive algorithms, including Timsort, combine run detection with rules for selecting which runs to merge. Different merge policies can have different performance guarantees. (arxiv.org)

Linked-list merge sort

For a linked list, merging can reconnect existing nodes instead of copying elements into an auxiliary array. This removes the need for a linear-size array buffer. The remaining control-space requirements depend on the implementation: a top-down version can use a logarithmic-depth call stack, whereas iterative arrangements can avoid recursion. The Linux kernel provides a practical stable linked-list sorting implementation organized around successive merges. (kernel.googlesource.com)

In-place array variants

An in-place algorithm uses little additional storage beyond its input. Array merging with substantially less auxiliary space is possible, but preserving stability and efficient running time makes the implementation more involved. The linear buffer of ordinary merge sort is therefore a characteristic of its standard implementation, not an impossibility result for every merge-based sorting method. (algs4.cs.princeton.edu)

Applications

External sorting

Merge-based methods are important in external sorting, where the data exceed available main memory. A typical procedure creates sorted runs that fit in memory, writes them to storage, and merges those runs into larger ones. The initial runs may be produced by a different sorting algorithm; the overall procedure is merge-based because of its combining phase. (opendsa.cs.vt.edu)

A multiway merge combines several runs at once using buffered input. Increasing the number of runs merged in a pass can reduce the number of passes over the data, provided enough memory is available for the buffers. In this setting, storage transfers and access patterns are often more important than the count of processor operations alone. (opendsa.cs.vt.edu)

Parallel sorting

Merge sort also supports parallel computing because its two recursive subproblems can be processed independently. However, parallelizing only the recursive sorting calls leaves the final sequential merge as a bottleneck. More scalable versions also divide the merging work among processors. Actual speedup depends on task granularity, scheduling, memory traffic, and the merge implementation. (tarjotin.cs.aalto.fi)

Stable record ordering

Stability is useful when sorting records by successive keys. For example, sorting first by name and then stably by department preserves name order within each department. Merge sort supplies this behavior together with a worst-case $n\log n$ time guarantee. (algs4.cs.princeton.edu)

Implementation trade-offs and optimizations

Compared with conventional quicksort, merge sort provides a deterministic worst-case bound and straightforward stability, but usually requires more array storage. Heapsort also provides a worst-case $O(n\log n)$ guarantee and can operate in place, but its conventional implementation is not stable. These differences concern the standard forms of the algorithms; specialized variants can change individual properties. (algs4.cs.princeton.edu)

Common optimizations include:

• Using insertion sort for small subarrays.
• Skipping a merge when the largest element of the left part is no greater than the smallest element of the right part.
• Alternating the roles of input and auxiliary arrays to reduce copying.

The boundary check can make an already sorted input take linear time, so an optimized merge sort need not retain the ordinary implementation’s $\Theta(n\log n)$ best-case behavior. These changes do not remove the standard worst-case $O(n\log n)$ guarantee. (algs4.cs.princeton.edu)

History

Merge sort is commonly credited to John von Neumann in 1945. It is an early example of an efficient computer sorting method built around recursive decomposition and merging, and remains a standard subject in the study of algorithms and their analysis. (cs.umd.edu)

References

1. Merge (Algorithms 4/e)algs4.cs.princeton.edu
2. Mergesortalgs4.cs.princeton.edu
3. Merge.javaalgs4.cs.princeton.edu
4. merge — Dictionary of Algorithms and Data Structuresxlinux.nist.gov
5. Merge Sortcs.umd.edu
6. A bargain for mergesorts (functional pearl) — How to prove your mergesort correct and stable, almost for freearxiv.org
7. Sorting Applicationsalgs4.cs.princeton.edu
8. Strategies for Stable Merge Sortingarxiv.org
9. tools/lib/list_sort.c — Linux source codekernel.googlesource.com
10. Simple in-place yet comparison-optimal Mergesortarxiv.org