Hard · Merge Sort
Understand → Visualise → Practice.
An inversion is a pair i < j with nums[i] > nums[j]. Merge sort counts whole blocks of inversions instead of checking every pair.
When right[j] is smaller than left[i], it is smaller than every remaining left value, adding len(left) − i inversions at once.
Count inversions in each half.
Choose the smaller front value.
A right-side choice jumps ahead of all remaining left values.
O(n log n) time and O(n) extra space.
Equal values are not inversions; take from the left when values are equal.
Read the full guides first: Sorting Algorithms and Their Trade-offs, Binary Search and Boundary Finding.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.