Merge Sort
This page introduces merge sort and its use for counting inversions.
Definition
Merge sort is an efficient, stable, comparison-based sorting algorithm.
Properties
Merge sort is based on divide and conquer: it splits the array into segments, sorts them, and merges them. It runs in \(\Theta (n \log n)\) in the best case, the worst case and the average case, and its space complexity is \(\Theta (n)\).
Merge sort can get by with only \(\Theta (1)\) auxiliary space, but for convenience it usually uses an auxiliary array as long as the original one.
Procedure
Merge
The heart of merge sort is the merge step: combining two sorted arrays a and b into one sorted array c.
Iterate over a[i] and b[j] from left to right, each time writing the smaller element to c[k]. When one array is exhausted, append the remaining elements of the other to c.
To keep the sort stable, the head of the first segment must go into c[k] as the minimum whenever it is less than or equal to the head of the second segment (a[i] <= b[j]), not only when it is strictly less (a[i] < b[j]).
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |
You can also use the std::merge function of the <algorithm> library. It is called in the same way as the pointer version above.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |
Top-down merge sort
- An array of length \(1\) is already sorted and does not need to be split any further.
- An array of length greater than \(1\) is quite likely not sorted. Split it into two segments and check whether each of the two arrays is sorted (using rule 1). If they are, merge them into one sorted array; otherwise, apply rule 2 again to each array that is not yet sorted, and then merge.
By induction, this procedure turns any array into a sorted array.
To guarantee the complexity of the sort, the array is usually split into two segments whose lengths are as equal as possible (\(\textit{mid} = \left\lfloor \dfrac{l + r}{2} \right\rfloor\)).
Implementation
Note that the ranges in the code below are \([l, r)\), \([l, \textit{mid})\) and \([\textit{mid}, r)\).
1 2 3 4 5 6 7 8 9 10 11 | |
1 2 3 4 5 6 7 8 9 | |
Bottom-up merge sort
We know that an array of length \(1\) is already sorted.
Cut the whole array into segments of length \(1\).
Going from left to right, merge the sorted runs of length \(1\) two at a time. This gives a series of sorted runs of length \(\le 2\).
Going from left to right, merge the sorted runs of length \(\le 2\) two at a time. This gives a series of sorted runs of length \(\le 4\).
Going from left to right, merge the sorted runs of length \(\le 4\) two at a time. This gives a series of sorted runs of length \(\le 8\).
...
Repeat this until the array consists of a single sorted run. That segment is the original array, sorted.
Why \(\le\) and not \(=\)
The length of the array is quite likely not \(2^x\). In that case the last segment may be shorter than the others, and it may also be left on its own, with no segment to merge with.
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | |
1 2 3 4 5 6 7 8 9 | |
Inversions
Further reading and reference implementations: inversions
An inversion is an ordered pair \((i, j)\) with \(i < j\) and \(a_i > a_j\).
A sorted array has no inversions. During a merge, each time the head of the second segment is taken out as the current minimum, count the elements remaining in the first segment; the sum of these counts is the number of inversions the merge removes. Merge sort therefore counts inversions in \(\Theta (n \log n)\). Inversions can also be counted with a Fenwick tree or a segment tree, again in \(O(n \log n)\); for a detailed explanation of that algorithm, see the corresponding part of Fenwick tree. Reference implementations of both algorithms are in the inversions section.
External links
- Merge Sort - GeeksforGeeks
- Merge sort - Wikipedia, the free encyclopedia (in Chinese)
- Inversion - Wikipedia, the free encyclopedia (in Chinese)
This page is an unofficial English translation of the original OI Wiki page (revision b469442a), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: partychicken, invalid-email-address, 24OI-bot, sshwy, ouuan, Xeonacid, NachtgeistW, Enter-tainer, minghu6, ksyx, iamtwz, mcendu, Junyan721113, weisi, Ir1d, zexpp5, IronSublimate, SaisycJiang, zirnc, Menci, untitledunrevised, Great-designer, Tiphereth-A, lychees, shawlleyw, megakite, c-forrest, ZnPdCo (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.