Skip to main content

Inversions Quick Guide

1. What Is an Inversion?​

For an array $A$:

An inversion is a pair of indices $(i, j)$ such that: $i < j \ &\ A[i] > A[j]$

Examples​

  • [1,2,3] → 0 inversions (already sorted).
  • [3,1,2] → (3,1), (3,2) → 2 inversions.
  • [7,3,5,1] → (7,3), (7,5), (7,1), (3,1), (5,1) → 5 inversions.

2. Why Do They Matter?​

a) Sorting Algorithms​

  • Bubble sort → each adjacent swap fixes 1 inversion.
  • Minimum swaps needed to sort = inversion count.

b) Permutation Parity​

  • Even number of inversions → even permutation.
  • Odd number of inversions → odd permutation.
  • Some puzzles (like Larry’s Array, 8-puzzle) can only solve even permutations.

c) Distance Metrics​

  • Kendall Tau distance = inversion count between two rankings.

3. How to Count Inversions​

A) Brute Force (O(n²))​

def count_inversions(arr):
    inversions = 0
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] > arr[j]:
                inversions += 1
    return inversions

B) Merge Sort Trick (O(n log n))​

  • Split array in half, count inversions in each half, and count cross-inversions while merging.
  • Standard technique for large n.

4. Quick Mental Trick (Small Arrays)​

  1. Take each element and count how many smaller numbers appear to its right.
  2. Sum them up.
  3. If result is even → even permutation, else odd permutation.

Example: [3, 14, 6, 8, 11]​

  • 3 → smaller to right? none → 0
  • 14 → smaller to right? 6,8,11 → 3
  • 6 → smaller to right? none → 0
  • 8 → smaller to right? none → 0
  • 11 → smaller to right? none → 0 Total = 3 → odd → unsolvable (Larry’s Array).

5. Where It Pops Up​

  • Sorting algorithm analysis (bubble sort, insertion sort).

  • Puzzle solvability:

    • Larry’s Array (3-element rotation).
    • 8-puzzle / 15-puzzle (sliding tiles).
    • Rubik’s cube parity checks.

  • Ranking comparison (machine learning, search engines).

6. Core Takeaways​

  • 0 inversions = sorted.
  • Inversion count = “how far from sorted.”
  • Parity (even vs odd) often matters more than the exact number.
  • If allowed operations can only change inversion count by even numbers (like 3-cycles), then odd inversion arrays are unsolvable.