Skip to main content

Counting Inversions

Learn Counting Inversions (Divide & Conquer, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Counting Inversions An inversion is a pair of positions i < j with a[i] > a[j] : two elements in the wrong order. The count measures how far an array is from sorted (0 for sorted, n(n-1)/2 for reversed). Checking all pairs takes O(n²) . A modified merge sort counts them in O(n log n) : when the merge takes an element from the right half, it jumps over all remaining left elements, so add that many inversions at once.

More lessons in Divide & Conquer