10810 - Ultra-QuickSort
To find number of adjacent swaps necessary to sort a given sequence of integers.
In a sequence , the pair is an inversion of if and . You have to find the inversions count of given sequences of length .
In the worst case of a completely unsorted list, ( , , ), number of swaps will equal:
where is the string length. Remembering that we have a huge , maximum number of swaps will equal:
which far exceeds the capacity of a 32-bit integer. Thus, use 64-bit integers for the inversions count.
Use long long to count swaps.
5 9 1 0 5 4 3 1 2 3 5 5 2 3 4 1 0
6 0 7