Merge Sort Inversions¶
Problem¶
Count the number of inversions in an array. An inversion is a pair (i, j) where i < j but nums[i] > nums[j].
Approach¶
Modified merge sort. During the merge step, when an element from the right half is placed before elements remaining in the left half, those left-half elements all form inversions with it.
When to Use¶
Counting disorder in sequences — "number of inversions", "how far from sorted", "Kendall tau distance". Modified merge sort counts cross-half inversions during the merge step. Also: rank correlation.
Complexity¶
| Time | O(n log n) |
| Space | O(n) |
Implementation¶
merge_sort_inversions ¶
Merge Sort Inversions — count inversions using merge sort.
Problem
Count the number of inversions in an array. An inversion is a pair (i, j) where i < j but nums[i] > nums[j].
Approach
Modified merge sort. During the merge step, when an element from the right half is placed before elements remaining in the left half, those left-half elements all form inversions with it.
When to use
Counting disorder in sequences — "number of inversions", "how far from sorted", "Kendall tau distance". Modified merge sort counts cross-half inversions during the merge step. Also: rank correlation.
Complexity
Time: O(n log n) Space: O(n)
count_inversions ¶
Return the number of inversions in nums.
count_inversions([2, 4, 1, 3, 5]) 3 count_inversions([5, 4, 3, 2, 1]) 10
Source code in src/algo/sorting/merge_sort_inversions.py
"""Tests for merge sort inversions."""
from hypothesis import given
from hypothesis import strategies as st
from algo.sorting.merge_sort_inversions import count_inversions
class TestCountInversions:
def test_basic(self) -> None:
assert count_inversions([2, 4, 1, 3, 5]) == 3
def test_sorted_array(self) -> None:
assert count_inversions([1, 2, 3, 4, 5]) == 0
def test_reverse_sorted(self) -> None:
assert count_inversions([5, 4, 3, 2, 1]) == 10
def test_single_element(self) -> None:
assert count_inversions([1]) == 0
def test_empty(self) -> None:
assert count_inversions([]) == 0
def test_two_elements_inverted(self) -> None:
assert count_inversions([2, 1]) == 1
@given(
data=st.lists(
st.integers(min_value=-100, max_value=100), min_size=0, max_size=50
),
)
def test_matches_brute_force(self, data: list[int]) -> None:
expected = sum(
1
for i in range(len(data))
for j in range(i + 1, len(data))
if data[i] > data[j]
)
assert count_inversions(data) == expected
Implement it yourself
Run: just challenge sorting merge_sort_inversions
Then implement the functions to make all tests pass.
Use just study sorting for watch mode.
Reveal Solution
merge_sort_inversions ¶
Merge Sort Inversions — count inversions using merge sort.
Problem
Count the number of inversions in an array. An inversion is a pair (i, j) where i < j but nums[i] > nums[j].
Approach
Modified merge sort. During the merge step, when an element from the right half is placed before elements remaining in the left half, those left-half elements all form inversions with it.
When to use
Counting disorder in sequences — "number of inversions", "how far from sorted", "Kendall tau distance". Modified merge sort counts cross-half inversions during the merge step. Also: rank correlation.
Complexity
Time: O(n log n) Space: O(n)
count_inversions ¶
Return the number of inversions in nums.
count_inversions([2, 4, 1, 3, 5]) 3 count_inversions([5, 4, 3, 2, 1]) 10