Count out-of-order pairs in a price series

Question

An "inversion" is a pair of positions i < j where the earlier value is greater than the later one. The total inversion count measures how far a series is from sorted, a crude gauge of downward disorder. Count all inversions. Return the number of inversions, in O(n log n) time. The brute-force pairwise count is O(n^2).

Accepted Answer

Piggyback on merge sort. Sort each half recursively (counting their internal inversions), then count "cross" inversions during the merge: when you take an element from the right half before some remaining left-half elements, every one of those remaining left elements is greater than it, so add the count of remaining left elements. Sum the three parts. Tracing [2, 4, 1, 3, 5]: the merges surface the three inversions (2,1), (4,1), and (4,3). Time O(n log n), space O(n) for the merge buffers. Edge cases: an already-sorted series has 0 inversions; a strictly decreasing series has the maximum n(n-…

Count out-of-order pairs in a price series

Your answer

More Coding questions