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.