= Merge sort
{title2=$T(n)=O(n\log n)$}
{wiki}
<Merge sort> is a <divide-and-conquer algorithm> that sorts a finite <array> by splitting it into contiguous halves, sorting each half using <recursion>, and combining the two <sorted arrays> with the <merge algorithm>. An empty or one-entry <array> is returned immediately. For length $n\geq2$, put the first $\lfloor n/2\rfloor$ entries on the left and the remaining $\lceil n/2\rceil$ on the right; the brackets are the <floor function> and <ceiling function>. Always choose the left head on equal keys to obtain <stable sorting>. This is the split, sort, combine structure taught in the MIT lecture notes.https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/90a37c49b07b105ea7a027abc67eddc6_MIT6_006F11_lec03.pdf[MIT 6.006 (2011), lecture 3: merge sort]{ref}
Take the concrete <input> <array>
$$
A=(7,2_a,5,2_b,9,1,4,3).
$$
The tags identify the entries originally at indices $1$ and $3$, counting from zero. Both keys are $2$; the tags are never compared. Reading downward in the figure follows the splits, then the returned <sorted arrays>. Arrows show dependencies; the level layout groups independent calls rather than giving their chronological execution order.
\Image[/merge-sort-split-and-merge.png]
{title=<Merge sort> splits into base cases and returns <sorted arrays>}
{description=The tagged keys 2a and 2b retain their original order through <stable sorting>. The <merge algorithm> makes 4, 6 and 7 head comparisons on the three returning levels, for 17 in total.}
The first two halves are $(7,2_a,5,2_b)$ and $(9,1,4,3)$. Their pairs split into one-entry base cases. Applying the <merge algorithm> gives the following fully worked return levels; each number in the last column counts only comparisons between two available heads.
|| Returning level
|| Resulting <sorted arrays>
|| Head comparisons
| Pairs
| $(2_a,7)$, $(2_b,5)$, $(1,9)$, $(3,4)$
| $1+1+1+1=4$
| Halves
| $(2_a,2_b,5,7)$, $(1,3,4,9)$
| $3+3=6$
| Whole <array>
| $(1,2_a,2_b,3,4,5,7,9)$
| $7$
In the left-half <merge algorithm>, the head pairs are $(2_a,2_b)$, $(7,2_b)$ and $(7,5)$; it takes $2_a,2_b,5$, then appends $7$. In the final <merge algorithm>, the head pairs are $(2_a,1)$, $(2_a,3)$, $(2_b,3)$, $(5,3)$, $(5,4)$, $(5,9)$ and $(7,9)$. It takes $1,2_a,2_b,3,4,5,7$, then appends $9$. Thus this precise version makes $4+6+7=17$ head comparisons and, ignoring identity tags, returns $(1,2,2,3,4,5,7,9)$.
The elegance of <merge sort> is that it creates exactly the structure its next step needs: two smaller <sorted arrays> make the larger ordering inexpensive. Once the whole <array> is sorted, equal keys are adjacent and <binary search> can serve repeated queries. <Stable sorting> also retains information that the keys alone do not express. If the left-half <merge algorithm> instead takes the right head on the $2_a=2_b$ tie, it returns $(2_b,2_a,5,7)$; the keys are sorted but <stable sorting> has failed.
For <time complexity>, assume each key comparison, entry access and entry copy has constant cost. The <merge algorithm> processes $n$ entries in $O(n)$ time. In <Big O notation>, the resulting <recurrence relation> is
$$
T(0),T(1)=O(1),\qquad T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+O(n)\quad(n\geq2).
$$
For $n=2^k$, the balanced levels contain $n$ entries each and there are $k=\log_2 n$ returning levels. Each costs $O(n)$, so the worst-case <time complexity> is $O(n\log n)$. For arbitrary $n$, there are at most $\lceil\log_2 n\rceil$ returning levels, each processing at most $n$ entries, giving the same bound. The worst-case number of head comparisons is also $O(n\log n)$. Here $\log_2$ is the base-two <logarithm>. The MIT notes give this level-by-level analysis for <merge sort>.https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/6d1ae5278d02bbecb5c4428928b24194_MIT6_006S20_lec3.pdf[MIT 6.006 (2020), lecture 3, page 5: merge sort analysis]{ref}
The conventional <array> implementation uses a reusable buffer of $n$ entries for the <merge algorithm>, together with $O(\log n)$ pending calls for <recursion>. Its auxiliary <space complexity> is therefore $O(n)$, beyond the original <array>. This bound describes that implementation. A <linked list> permits a <merge algorithm> that reconnects existing nodes; its storage accounting differs from copying <array> entries into a buffer.
For a short <algorithm correctness> outline, the empty and one-entry base cases are sorted. Assuming <recursion> correctly sorts both shorter halves, the <merge algorithm> returns all their entries in order. Equal keys within a half keep their relative order by the same argument applied to the smaller call; across halves, every left entry originally preceded every right entry, so taking left first preserves <stable sorting>. Both half-lengths decrease for $n\geq2$, establishing termination.
Back to article page
