Sign in to watch this lesson
Algorithms - Sorting and Searching · 5:16
Merge Sort and Counting Inversions
Merge sort splits [2, 4, 1, 3, 5] in half until every piece is a single value, then merges back up with two pointers. In the top merge, every time a right-half value jumps ahead of the values still waiting on the left it forms an inversion with each of them, so one extra line (add mid - i) counts all inversions in O(n log n). We see why every level of the recursion costs n, measure the comparisons against the lower bound and the brute-force count on this Mac, and cover the traps: ties, 64-bit counters, one shared buffer, and what libc++'s std::stable_sort does.
You will learn
- Implement merge sort with one shared buffer and explain why every recursion level costs O(n), giving Theta(n log n) in every case
- Count inversions during the merge by adding mid - i whenever a right-half value is taken, and argue why this counts every inversion exactly once
- Handle ties with <= so equal values are not counted and the sort stays stable, and store the count in a 64-bit integer
- Describe how libc++'s std::stable_sort uses a merge sort with a temporary buffer and when it falls back to an in-place merge