Merge Sort: Working, Example, and Complexity Analysis

Verified Sources

Sep 11, 2026

Merge sort orders an array by repeatedly splitting it into smaller subarrays, sorting those subarrays, and combining them in sorted order. It is based on the divide-and-conquer paradigm.

The algorithm has three logical phases:

Divide: Split the array into two approximately equal halves.
Conquer: Recursively sort each half.
Combine: Merge the two sorted halves into one sorted array.

The recursion stops when a subarray contains zero or one element because such a subarray is already sorted.

Merge sort is generally stable and has $\Theta(n \log n)$ time complexity in the best, average, and worst cases. Standard array implementations use $\Theta(n)$ auxiliary space.

Merge sort - Overview, algorithm, stability, recurrence, and complexity characteristics. ↩ ↩²
Merge Sort - GeeksforGeeks - Algorithm steps, recurrence relation, and implementation details. ↩

Learn Merge Sort in 13 minutes

Core idea: merge two sorted arrays

The most important operation is the merge procedure.

Suppose the two sorted halves are:

Left half: $[4, 10, 18]$
Right half: $[2, 7, 15]$

Use one pointer for each half:

Compare $4$ and $2$ ; copy $2$ .
Compare $4$ and $7$ ; copy $4$ .
Compare $10$ and $7$ ; copy $7$ .
Compare $10$ and $15$ ; copy $10$ .
Compare $18$ and $15$ ; copy $15$ .
Copy the remaining $18$ .

Result:

[2,4,7,10,15,18]

Each element is examined at most a constant number of times during a merge, so merging two halves containing a total of $n$ elements takes $\Theta(n)$ time.

Merge Sort Algorithm - Divide-and-conquer analysis, Master Theorem solution, and space analysis. ↩

Merge Sort Process

1
Step 1
Split the array into two halves. For an array of length $n$ , the halves contain approximately $n/2$ elements each.
2
Step 2
Recursively divide each half until every subarray contains one element. A one-element subarray is the base case because it is already sorted.
3
Step 3
Compare the first unprocessed element in each sorted subarray. Copy the smaller element into a temporary result array, then advance that subarray's pointer.
4
Step 4
When one subarray is exhausted, copy all remaining elements from the other subarray. They are already sorted.
5
Step 5
Merge progressively larger sorted subarrays until the complete array has been reconstructed in sorted order.

Worked example

Consider the input:

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

Because the input length is $7$ , the divisions are not perfectly equal, but the subarrays differ in size by at most one.

Division phase

The final one-element subarrays are:

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

Merge phase

Merge neighboring one-element arrays:

[27] + [43] \rightarrow [27,43]

[3] + [9] \rightarrow [3,9]

[82] + [10] \rightarrow [10,82]

Now merge larger subarrays:

[38] + [27,43] \rightarrow [27,38,43]

[3,9] + [10,82] \rightarrow [3,9,10,82]

Finally:

[27,38,43] + [3,9,10,82] \rightarrow [3,9,10,27,38,43,82]

Therefore, the sorted output is:

\boxed{[3,9,10,27,38,43,82]}

MERGE-SORT(A, left, right)
    if left >= right
        return

    middle = floor((left + right) / 2)

    MERGE-SORT(A, left, middle)
    MERGE-SORT(A, middle + 1, right)

    MERGE(A, left, middle, right)


MERGE(A, left, middle, right)
    create temporary array result

    i = left
    j = middle + 1

    while i <= middle and j <= right
        if A[i] <= A[j]
            append A[i] to result
            i = i + 1
        else
            append A[j] to result
            j = j + 1

    append remaining elements from the left half
    append remaining elements from the right half

    copy result back into A[left...right]

Why the merge is correct

Assume the left and right halves are already sorted.

At every iteration, the algorithm compares the smallest unprocessed element from each half. The smaller of these two elements must be the smallest element remaining overall:

Every unprocessed element in the left half is at least as large as the left pointer.
Every unprocessed element in the right half is at least as large as the right pointer.
Therefore, choosing the smaller pointer value is safe.

This is a loop invariant: after each merge iteration, the output contains the smallest elements in sorted order. When one half is exhausted, all remaining elements in the other half are larger than or equal to the elements already copied, so appending them preserves sorted order.

By induction:

One-element arrays are sorted.
If two recursively sorted halves are merged correctly, their combined array is sorted.
Therefore, the final array is sorted.

Using <= when values are equal causes the element from the left half to be selected first, preserving stability.

Merge Sort – Algorithm, Source Code, Time Complexity - Stability and merge implementation details. ↩

Key insight

Merge sort does not search for a favorable input arrangement. It always divides the data into halves and performs linear merging at each level, which makes its running time predictable.

Complexity calculation

Let $T(n)$ denote the running time for sorting $n$ elements.

1. Divide cost

Finding the middle index and identifying the two subarrays takes constant time:

\Theta(1)

2. Recursive cost

The algorithm recursively sorts two subarrays, each of size approximately $n/2$ :

2T\left(\frac{n}{2}\right)

3. Merge cost

The merge operation processes all $n$ elements in the two halves:

\Theta(n)

Therefore, the recurrence is:

T(n)=2T\left(\frac{n}{2}\right)+\Theta(n)

with the base case:

T(1)=\Theta(1)

This recurrence is the standard merge-sort recurrence.2

Merge sort - Overview, algorithm, stability, recurrence, and complexity characteristics. ↩
Merge Sort Algorithm - Divide-and-conquer analysis, Master Theorem solution, and space analysis. ↩

Complexity calculation using a recursion tree

At each recursion-tree level, the total merge work is $\Theta(n)$ .

Level	Number of subproblems	Size of each subproblem	Total merge work
$0$	$1$	$n$	$\Theta(n)$
$1$	$2$	$n/2$	$\Theta(n)$
$2$	$4$	$n/4$	$\Theta(n)$
$i$	$2^i$	$n/2^i$	$\Theta(n)$
$\log_2 n$	$n$	$1$	$\Theta(n)$ or base-case work

The height of the tree is:

\log_2 n

Since each level contributes $\Theta(n)$ work and there are $\Theta(\log n)$ levels:

T(n)=\Theta(n)\cdot\Theta(\log n)

Thus:

\boxed{T(n)=\Theta(n\log n)}

The logarithm's base does not change the asymptotic class because:

\log_b n=\frac{\log_a n}{\log_a b}

The conversion factor is constant.

Complexity calculation using the Master Theorem

The Master Theorem analyzes recurrences of the form:

T(n)=aT\left(\frac{n}{b}\right)+f(n)

For merge sort:

$a=2$ : two recursive subproblems
$b=2$ : each subproblem has half the input size
$f(n)=\Theta(n)$ : merging takes linear time

Calculate:

n^{\log_b a}=n^{\log_2 2}=n

Therefore:

f(n)=\Theta(n)=\Theta\left(n^{\log_2 2}\right)

This is the balanced case of the Master Theorem, which adds a logarithmic factor:

T(n)=\Theta(n\log n)

Hence, merge sort requires:

\boxed{\Theta(n\log n)}

time in the best, average, and worst cases for the standard implementation.2

Merge Sort - GeeksforGeeks - Algorithm steps, recurrence relation, and implementation details. ↩
Merge Sort Algorithm - Divide-and-conquer analysis, Master Theorem solution, and space analysis. ↩

Asymptotic Time Comparison

Relative growth for representative input sizes; values are proportional to the stated complexity.

Space complexity

For an array implementation:

The temporary merge array can hold up to $n$ elements: $\Theta(n)$ .
The recursion stack has height $\Theta(\log n)$ .
The total auxiliary space is:

\Theta(n)+\Theta(\log n)=\Theta(n)

Therefore:

\boxed{\text{Auxiliary space}=\Theta(n)}

The recursion stack alone is $\Theta(\log n)$ , but the temporary arrays dominate the space usage.

Complexity summary

Property	Complexity
Best-case time	$\Theta(n\log n)$
Average-case time	$\Theta(n\log n)$
Worst-case time	$\Theta(n\log n)$
Auxiliary space for arrays	$\Theta(n)$
Recursion-stack space	$\Theta(\log n)$
Stability	Yes, when equal elements are taken from the left first
In-place in the standard array implementation	No

A linked-list implementation can merge nodes with less auxiliary storage, while specialized in-place array variants exist but are more complicated and may have different practical performance characteristics.2

Merge Sort Algorithm - Divide-and-conquer analysis, Master Theorem solution, and space analysis. ↩
Merge sort - Overview, algorithm, stability, recurrence, and complexity characteristics. ↩
Time Complexity of Merge Sort - Comparison of time and space complexity with other sorting algorithms. ↩

Common misconception

The divide step is not the source of the n log n cost by itself. The logarithmic factor comes from the number of halving levels, while the linear factor comes from merging all elements at every level.

Important Questions and Edge Cases

Merge Sort Essentials

1 / 6

Question · Term

What is the base case?

Click to reveal

Answer · Definition

A subarray with zero or one element. It is already sorted.

How to Analyze Merge Sort in an Exam

1
Step 1
There are two calls on subproblems of size approximately $n/2$ , giving $2T(n/2)$ .
2
Step 2
The merge scans all elements once, giving $\Theta(n)$ .
3
Step 3
Use $T(n)=2T(n/2)+\Theta(n)$ with $T(1)=\Theta(1)$ .
4
Step 4
Use a recursion tree or the Master Theorem. Here, $a=2$ , $b=2$ , and $f(n)=\Theta(n)$ .
5
Step 5
Because $n^{\log_2 2}=n$ matches $f(n)$ , the result is $T(n)=\Theta(n\log n)$ .
6
Step 6
The temporary merge array contributes $\Theta(n)$ and the recursion stack contributes $\Theta(\log n)$ , so total auxiliary space is $\Theta(n)$ .

Knowledge Check

Question 1 of 5

Q1Single choice

What is the main operation responsible for the linear work at each level of merge sort?

Selecting a random pivot

Merging two sorted subarrays

Comparing every pair of elements

Building a heap

Explore Related Topics

Differentiating Divide & Conquer, Greedy Method, and Dynamic Programming

Understanding Belady's Anomaly in Operating Systems

Belady's Anomaly shows that, for some page‑replacement policies, adding more physical frames can increase the number of page faults.

FIFO (a non‑stack algorithm) does not satisfy the inclusion property and can exhibit the anomaly.
On the reference string  $1,2,3,4,1,2,5,1,2,3,4,5$ , FIFO yields $9$ faults with $3$ frames but $10$ faults with $4$ frames.
Stack algorithms such as LRU or Optimal obey $M(N,t)\subseteq M(N+1,t)$ , guaranteeing that more frames never raise fault counts.
Designing a virtual‑memory system with stack‑based replacement eliminates Belady's Anomaly.

Complexity Analysis: Best Case, Worst Case, and Average Case

The material introduces best‑case, worst‑case, and average‑case complexity as three distinct functions describing an algorithm’s running time on inputs of size  $n$ , explains how they are formally defined, and shows why worst‑case analysis is usually preferred.

Best case: $T_{\text{best}}(n)=\min_{I\in\mathcal I_n} T(I)$ , the minimum time over all inputs of size  $n$ .
Worst case: $T_{\text{worst}}(n)=\max_{I\in\mathcal I_n} T(I)$ , giving a guaranteed upper bound.
Average case: $T_{\text{avg}}(n)=\sum_{I\in\mathcal I_n}P(I)\,T(I)$ , requiring an explicit input probability model.
Linear search illustrates the three cases: $\Theta(1)$ best, $\Theta(n)$ worst, and $\Theta(n)$ average (expected $\frac{n+1}{2}$ comparisons).
Worst‑case analysis is favored because it needs no probabilistic assumptions and ensures reliability for all inputs, especially in real‑time or safety‑critical systems.

Browse all research articles

Merge Sort: Working, Example, and Complexity Analysis

Footnotes

Learn Merge Sort in 13 minutes

Core idea: merge two sorted arrays

Footnotes

Merge Sort Process

Worked example

Division phase

Merge phase

Why the merge is correct

Footnotes

Key insight

Complexity calculation

1. Divide cost

2. Recursive cost

3. Merge cost

Footnotes

Complexity calculation using a recursion tree

Complexity calculation using the Master Theorem

Footnotes

Asymptotic Time Comparison

Space complexity

Complexity summary

Footnotes

Common misconception

Important Questions and Edge Cases

Merge Sort Essentials

What is the base case?

How to Analyze Merge Sort in an Exam

Knowledge Check

Explore Related Topics