Count Inversions in Array in DSA Rust - Execution Trace

Concept Flow - Count Inversions in Array

Start with array

↓

Divide array into two halves

↓

Recursively count inversions in left half

↓

Recursively count inversions in right half

↓

Merge two halves while counting split inversions

↓

Sum left, right, and split inversions

↓

Return total inversion count

The array is split into halves recursively, counting inversions in each half and during merge, then sums all counts.

Execution Sample

DSA Rust

fn merge_sort_count(arr: &mut [i32]) -> usize {
    if arr.len() <= 1 { return 0; }
    let mid = arr.len() / 2;
    let mut count = merge_sort_count(&mut arr[..mid]);
    count += merge_sort_count(&mut arr[mid..]);
    count += merge(arr, mid);
    count
}

fn merge(arr: &mut [i32], mid: usize) -> usize { /* merges and counts inversions */ }

This code recursively sorts the array and counts inversions by merging halves.

Execution Table

Step	Operation	Array State	Pointer Changes	Visual State
1	Start with full array	[2, 4, 1, 3, 5]	head=0, mid=2, tail=5	2 -> 4 -> 1 -> 3 -> 5 -> null
2	Divide into left half	[2, 4]	head=0, mid=1	2 -> 4 -> null
3	Divide left half further	[2]	single element	2 -> null
4	Divide left half further	[4]	single element	4 -> null
5	Merge left half [2] and [4]	[2,4]	i=0,j=1	2 -> 4 -> null (no inversion)
6	Divide right half	[1,3,5]	head=2, mid=3	1 -> 3 -> 5 -> null
7	Divide right half further	[1]	single element	1 -> null
8	Divide right half further	[3,5]	head=3, mid=4	3 -> 5 -> null
9	Divide right half further	[3]	single element	3 -> null
10	Divide right half further	[5]	single element	5 -> null
11	Merge right half [3] and [5]	[3,5]	i=3,j=4	3 -> 5 -> null (no inversion)
12	Merge right half [1] and [3,5]	[1,3,5]	i=2,j=3	1 -> 3 -> 5 -> null (no inversion)
13	Merge full array [2,4] and [1,3,5]	[1,2,3,4,5]	i=0,j=2	1 -> 2 -> 3 -> 4 -> 5 -> null (inversions counted)
14	Count split inversions during merge	Count=3	Pointers moved accordingly	Final sorted array with inversion count 3
15	Return total inversion count	3	All merges done	Sorted array: 1 -> 2 -> 3 -> 4 -> 5 -> null

💡 All subarrays merged and counted, recursion ends with total inversion count 3

Variable Tracker

Variable	Start	After Step 5	After Step 11	After Step 12	After Step 13	Final
arr	[2,4,1,3,5]	[2,4,1,3,5]	[2,4,1,3,5]	[2,4,1,3,5]	[1,2,3,4,5]	[1,2,3,4,5]
count	0	0	0	0	3	3
head	0	0	2	2	0	0
mid	2	1	4	3	2	2
tail	5	2	5	5	5	5
i (left pointer)	0	0	3	2	0	0
j (right pointer)	2	2	4	3	2	2

Key Moments - 3 Insights

Why do we count inversions during the merge step and not just when dividing?

Because inversions occur between elements in different halves, counting during merge (see Step 13 and 14) captures these 'split' inversions that division alone misses.

How does the pointer movement during merge help count inversions?

When an element from the right half is placed before one from the left, all remaining left elements form inversions (Step 13 shows pointers i and j moving and counting 3 inversions).

Why does the recursion stop when subarray length is 1?

A single element cannot have inversions (Step 3,7,9,10), so recursion stops to start merging and counting.

Visual Quiz - 3 Questions

Look at the execution_table at Step 13, what is the array state after merging?

A [1, 2, 3, 4, 5]

B [2, 4, 1, 3, 5]

C [1, 3, 5, 2, 4]

D [5, 4, 3, 2, 1]

💡 Hint

Check the 'Array State' column at Step 13 in execution_table

At which step does the total inversion count become 3?

A Step 5

B Step 12

C Step 14

D Step 10

💡 Hint

Look at the 'Count split inversions during merge' row in execution_table

If the array was already sorted, how would the inversion count change in variable_tracker?

A It would increase to the array length

B It would remain 0 throughout

C It would be negative

D It would be equal to the number of elements

💡 Hint

Refer to 'count' variable in variable_tracker showing inversion counts

Concept Snapshot

Count Inversions in Array using Merge Sort:
- Split array recursively into halves
- Count inversions in left and right halves
- Count split inversions during merge
- Sum all counts for total inversions
- Runs in O(n log n) time

Full Transcript

Counting inversions in an array means finding how many pairs are out of order. We use a merge sort approach: split the array into halves, count inversions in each half recursively, then count inversions between halves while merging. The merge step compares elements from left and right halves; when an element from the right half is placed before one from the left, it counts as many inversions as remaining elements in the left half. This process continues until the whole array is sorted and all inversions are counted. The example array [2,4,1,3,5] has 3 inversions counted during the final merge. The recursion stops when subarrays have one element, as no inversions exist there. This method efficiently counts inversions in O(n log n) time.

Practice

1. What does the term inversion mean in the context of an array?

easy

A. A pair of elements where the first is greater than the second and appears before it

B. A pair of elements where the first is smaller than the second and appears before it

C. The total number of elements in the array

D. The sum of all elements in the array

Solution

1. Step 1: Understand the definition of inversion

   An inversion is a pair of elements where the first element is greater than the second and appears before it in the array.

2. Step 2: Compare options with definition

   A pair of elements where the first is greater than the second and appears before it matches this definition exactly, while others describe different concepts.

3. Final Answer:

   A pair of elements where the first is greater than the second and appears before it -> Option A

4. Quick Check:

   Inversion = pair (i, j) with i < j and arr[i] > arr[j] [OK]

Hint: Inversion means earlier bigger number than a later one [OK]

Common Mistakes:

• Confusing inversion with sorted order
• Thinking inversion counts total elements
• Mixing up greater and smaller element order

2. Which Rust code snippet correctly declares a function to count inversions in an array slice?

easy

A. fn count_inversions(arr: &[i32]) -> i32 { 0 }

B. fn count_inversions(arr: Vec i32 { 0 }

C. fn count_inversions(arr: &[i32]) -> usize { 0 }

D. fn count_inversions(arr: &mut [i32]) -> usize { 0 }

Solution

1. Step 1: Identify correct function signature for counting inversions

   The function should take an immutable slice of integers and return the count as usize (non-negative integer).

2. Step 2: Compare options

   fn count_inversions(arr: &[i32]) -> usize { 0 } uses &[i32] for input and usize for output, which is correct. fn count_inversions(arr: Vec i32 { 0 } takes ownership (Vec) and returns i32 (can be negative). fn count_inversions(arr: &mut [i32]) -> usize { 0 } uses mutable slice unnecessarily. fn count_inversions(arr: &[i32]) -> i32 { 0 } returns i32 which can be negative, not ideal for count.

3. Final Answer:

   fn count_inversions(arr: &[i32]) -> usize { 0 } -> Option C

4. Quick Check:

   Immutable slice input + usize output = correct signature [OK]

Hint: Use &[i32] input and usize output for count functions [OK]

Common Mistakes:

• Using Vec instead of slice for input
• Returning signed integer for count
• Using mutable slice when not needed

3. What is the output of the following Rust code snippet counting inversions?

fn main() {
    let arr = [2, 4, 1, 3, 5];
    let mut count = 0;
    for i in 0..arr.len() {
        for j in i+1..arr.len() {
            if arr[i] > arr[j] {
                count += 1;
            }
        }
    }
    println!("{}", count);
}

medium

A. 4

B. 3

C. 2

D. 5

Solution

1. Step 1: Identify all inversion pairs in the array

   Array: [2, 4, 1, 3, 5]. Inversions are (2,1), (4,1), (4,3). Total 3 inversions.

2. Step 2: Confirm count from nested loops

   Loops check all pairs i < j. Each inversion increments count by 1. Final count is 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Count inversions by pairs = 3 [OK]

Hint: Count pairs where earlier number is bigger than later [OK]

Common Mistakes:

• Counting non-inversion pairs
• Missing some inversion pairs
• Confusing indices order

4. The following Rust code attempts to count inversions but has a bug. What is the bug?

fn count_inversions(arr: &[i32]) -> usize {
    let mut count = 0;
    for i in 0..arr.len() {
        for j in 0..arr.len() {
            if arr[i] > arr[j] {
                count += 1;
            }
        }
    }
    count
}

medium

A. Inner loop should start from i+1, not 0

B. Count variable should be i32, not usize

C. Function should take mutable slice

D. Comparison operator should be < instead of >

Solution

1. Step 1: Analyze loop ranges for counting inversions

   Inversion counts pairs where i < j and arr[i] > arr[j]. Inner loop starting at 0 compares all pairs including i >= j, causing double counting and invalid pairs.

2. Step 2: Correct inner loop start index

   Inner loop should start at i+1 to ensure only pairs with i < j are counted once.

3. Final Answer:

   Inner loop should start from i+1, not 0 -> Option A

4. Quick Check:

   Loop indices must ensure i < j for correct inversion count [OK]

Hint: Inner loop must start after outer index to avoid double count [OK]

Common Mistakes:

• Starting inner loop at 0 causing double counting
• Using wrong comparison operator
• Changing input slice to mutable unnecessarily

5. Given the array [8, 4, 2, 1], what is the number of inversions? Use the merge sort based approach to count inversions efficiently.

hard

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Understand merge sort inversion counting

   Merge sort counts inversions by counting how many elements from right subarray are placed before left subarray elements during merge.

2. Step 2: Count inversions in [8,4,2,1]

   Pairs: (8,4), (8,2), (8,1), (4,2), (4,1), (2,1) total 6 inversions.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   All pairs where left > right count to 6 [OK]

Hint: Count pairs where left number bigger than right during merge [OK]

Common Mistakes:

• Counting only adjacent pairs
• Missing some inversion pairs
• Confusing merge sort steps