299 - Train Swapping

The idea is to count inversions while sorting.

Book: Algorithm Design.

Here is the execution of merge sort with counting inversions:

Example: 4  3  2  1  

merge_sort(left=0  right=1)

merge_sort(left=0  right=0)

merge_sort(left=1  right=1)

merge(left=0  mid=1   right=1)

4 is greater than 3,  1 more inversion(s)

3  4  2  1  

merge_sort(left=2  right=3)

merge_sort(left=2  right=2)

merge_sort(left=3  right=3)

merge(left=2  mid=3   right=3)

2 is greater than 1,  1 more inversion(s)

3  4  1  2  

merge(left=0  mid=2   right=3)

3 is greater than 1,  2 more inversion(s)

3 is greater than 2,  2 more inversion(s)

1  2  3  4  

Inversions=6