Assume the elements are to be sorted in non-decreasing order. Given a sequence of n elements (also called keys) a[1], …, a[n], the idea is to imagine them split into two sets a[1], …, a[n/2] and a[n/2+1], …, a[n]. Each set is individually sorted, and the resulting sorted sequences are merged to produce a single sorted sequence of n elements.

Divide: partition the array into two sublists S₁ and S₂ with n/2 elements each.
Conquer: recursively sort S₁ and S₂.
Combine: merge S₁ and S₂ into a single sorted group.

Algorithm MergeSort(low, high)

Algorithm MergeSort(low, high)
// a[low:high] is a global array to be sorted.
// Small(P) is true if there is only one element.
{
    if (low < high) then          // if there are more than one element
    {
        // Divide P into subproblems
        mid := ⌊(low + high) / 2⌋;
        // Solve the subproblems
        MergeSort(low, mid);
        MergeSort(mid + 1, high);
        // Combine the solutions
        Merge(low, mid, high);
    }
}

Algorithm Merge(low, mid, high)

Algorithm Merge(low, mid, high)
/* a[low:high] is a global array containing two sorted subsets
   in a[low:mid] and a[mid+1:high]. This algorithm merges these
   two sets into a single set residing in a[low:high].
   b[ ] is an auxiliary global array. */
{
    h := low; i := low; j := mid + 1;
    while ((i ≤ mid) and (j ≤ high)) do
    {
        if (a[i] ≤ a[j]) then
        {
            b[h] := a[i]; i := i + 1;
        }
        else
        {
            b[h] := a[j]; j := j + 1;
        }
        h := h + 1;
    }
    if (i > mid) then
        for k := j to high do
        {
            b[h] := a[k]; h := h + 1;
        }
    else
        for k := i to mid do
        {
            b[h] := a[k]; h := h + 1;
        }
    for k := low to high do a[k] := b[k];
}

Examples

Ex. 1: a[1:10] = (310, 285, 179, 662, 351, 423, 861, 254, 450, 520). Trace merge sort on this array.

Ex. 2: a[1:7] = E, X, A, M, P, L, E

Phase	Step	Sublists
Divide	Start	[E X A M P L E]
	Split	[E X A M] [P L E]
	Split again	[E X] [A M] [P L] [E]
Single elements	–	[E] [X] [A] [M] [P] [L] [E]
Conquer / Merge	Merge pairs	[E X] [A M] [L P] [E]
	Merge again	[A E M X] [E L P]
	Final merge	[A E E L M P X]

Tree of calls of MergeSort(1, 7)

Tree of calls of Merge

Each box is Merge(low, mid, high).

Tracing Merge(1, 4, 7)

Merging (A, E, M, X) and (E, L, P) gives (A, E, E, L, M, P, X). Here low = 1, mid = 4 and high = 7.

Index	[1]	[2]	[3]	[4]	[5]	[6]	[7]
a	A	E	M	X	E	L	P

h	i	j	i ≤ mid and j ≤ high	Test a[i] ≤ a[j]	Action	b so far
1	1	5	1 ≤ 4 and 5 ≤ 7	A ≤ E, true	copy a[1] to b[1]	A
2	2	5	2 ≤ 4 and 5 ≤ 7	E ≤ E, true	copy a[2] to b[2]	A E
3	3	5	3 ≤ 4 and 5 ≤ 7	M ≤ E, false	copy a[5] to b[3]	A E E
4	3	6	3 ≤ 4 and 6 ≤ 7	M ≤ L, false	copy a[6] to b[4]	A E E L
5	3	7	3 ≤ 4 and 7 ≤ 7	M ≤ P, true	copy a[3] to b[5]	A E E L M
6	4	7	4 ≤ 4 and 7 ≤ 7	X ≤ P, false	copy a[7] to b[6]	A E E L M P
7	4	8	8 ≰ 7, loop ends	–	i = 4 ≤ mid, so copy a[4] to b[7]	A E E L M P X

The leftover elements are copied with for k := i to mid, here k = 4 to 4. Finally b[1..7] is copied back to a[1..7].

Limitations

It needs an auxiliary array with the same amount of storage as the input array, so this algorithm is not an in-place algorithm.
It needs stack space for recursion, because the algorithm is designed in a top-down fashion. The stack takes O(log₂n) space.

Time complexity

T(n) = 1               when n = 1
     = 2T(n/2) + cn    otherwise

When n = 2^k:

T(n) = 2[2T(n/4) + cn/2] + cn
     = 2²T(n/2²) + 2cn
       ⋮
     = 2ᵏT(n/2ᵏ) + k·cn
     = n + log₂n · cn

⇒ T(n) = O(n log₂ n)

Space complexity

Merge sort needs an auxiliary array of size n, plus O(log₂n) stack space for the recursion, so the extra space is O(n).

Merge sort is a stable sorting method (see the notes on quick sort).

Design and Analysis of Algorithms

Merge Sort