Divide and conquer Version of 08/03/20
splits each array Counting Inversions: Example
into left and right
subarrays.
1 5 4 8 10 2 6 9 12 11 3 7
1 5 4 8 10 2 6 9 12 11 3 7
1 5 4 8 10 2 6 9 12 11 3 7
1 5 4 8 10 2 6 9 12 11 3 7
1 5 8 10 6 9 11 3
1
Bottom level has 0
inversions.
Counting Inversions: Example
Compare blue and
green to see if
next level up has 1 5 4 8 10 2 6 9 12 11 3 7
either 0 or 1.
1 5 4 8 10 2 6 9 12 11 3 7
1 5 4 8 10 2 6 9 12 11 3 7
0 1 5 4 0 8 10 2 0 6 9 12 1 11 3 7
1 5 8 10 6 9 11 3
2
When calculating
blue-green
Counting Inversions: Example
inversions, merge
blue lists and
green lists so 1 5 4 8 10 2 6 9 12 11 3 7
blue-green list is
sorted
1 5 4 8 10 2 6 9 12 11 3 7
1 5 4 8 10 2 6 9 12 11 3 7
0 1 5 4 0 8 10 2 0 6 9 12 1 3 11 7
1 5 8 10 6 9 11 3
3
When calculating
blue-green
Counting Inversions: Example
inversions, merge
blue lists and
green lists so 1 5 4 8 10 2 6 9 12 11 3 7
blue-green list is
sorted
1 5 4 8 10 2 6 9 12 11 3 7
1 5 4 8 10 2 6 9 12 11 3 7
0 1 5 4 0 8 10 2 0 6 9 12 1 3 11 7
4
Counting Inversions: Example
1 5 4 8 10 2 6 9 12 11 3 7
1 5 4 8 10 2 6 9 12 11 3 7
1 1 5 4 2 8 10 2 0 6 9 12 2 11 3 7
1 2 0 1
0 1 5 4 0 0 8 10 2 0 0 6 9 12 0 1 3 11 7 0
Each level is split into Blue left and Green Right.
Blue and Green subarrays are pre-sorted and the # of their internal inversions is known.
Add Blue inversions + Green Inversions plus Blue-Green inversions to get total inversions
Total inversions will be on side of array.
BG inversions will be shown directly under array 5
When calculating
blue-green
Counting Inversions: Example
inversions, merge
blue lists and
green lists so 1 5 4 8 10 2 6 9 12 11 3 7
blue-green list is
sorted
1 5 4 8 10 2 6 9 12 11 3 7
1 1 4 5 2 2 8 10 0 6 9 12 2 3 7 11
1 2 0 1
0 1 5 4 0 0 8 10 2 0 0 6 9 12 0 1 3 11 7 0
6
When calculating
blue-green
Counting Inversions: Example
inversions, merge
blue lists and
green lists so 1 5 4 8 10 2 6 9 12 11 3 7
blue-green list is
sorted
1 5 4 8 10 2 6 9 12 11 3 7
1 1 4 5 2 2 8 10 0 6 9 12 2 3 7 11
7
When calculating
blue-green
Counting Inversions: Example
inversions, merge
blue lists and
green lists so 1 5 4 8 10 2 6 9 12 11 3 7
blue-green list is
sorted
5 1 2 4 5 8 10 8 3 6 7 9 11 12
2 6
1 1 4 5 2 2 8 10 0 6 9 12 2 3 7 11
Add Blue inversions + Green Inversions plus Blue-Green inversions to get total inversions
Total inversions will be on side of array.
BG inversions will be shown directly under array
8
When calculating
blue-green
Counting Inversions: Example
inversions, merge
blue lists and
green lists so 1 5 4 8 10 2 6 9 12 11 3 7
blue-green list is
sorted
5 1 2 4 5 8 10 8 3 6 7 9 11 12
Add Blue inversions + Green Inversions plus Blue-Green inversions to get total inversions
Total inversions will be on side of array.
BG inversions will be shown directly under array
9
When calculating
blue-green Counting Inversions: Example
inversions, merge
blue lists and
green lists so 22 1 2 3 4 5 6 7 8 9 10 11 12
blue-green list is
9
sorted
5 1 2 4 5 8 10 8 3 6 7 9 11 12
Add Blue inversions + Green Inversions plus Blue-Green inversions to get total inversions
Total inversions will be on side of array.
BG inversions will be shown directly under array
10
Counting Inversions: Complete Worked Example
22 1 5 4 8 10 2 6 9 12 11 3 7
9
5 1 5 4 8 10 2 8 6 9 12 11 3 7
2 6
1 1 5 4 2 8 10 2 0 6 9 12 2 11 3 7
1 2 0 1
0 1 5 4 0 0 8 10 2 0 0 6 9 12 0 1 11 3 7 0
0 0 0 1
0 1 5 0 0 8 10 0 0 6 9 0 0 11 3 0
11
Counting Inversions: Complete Worked Example
22 1 2 3 4 5 6 7 8 9 10 11 12
9
5 1 2 4 5 8 10 8 3 6 7 9 11 12
2 6
1 1 4 5 2 2 8 10 0 6 9 12 2 3 7 11
1 2 0 1
0 1 5 4 0 0 8 10 2 0 0 6 9 12 0 1 3 11 7 0
0 0 0 1
0 1 5 0 0 8 10 0 0 6 9 0 0 11 3 0
Blue tree leaves are the original array order 12