Check out the resources on the page's right side to learn more about merge sort. The video tutorial is by Gayle Laakmann McDowell, author of the best-selling interview book Cracking the Coding Interview.
In an array, , the elements at indices and (where ) form an inversion if . In other words, inverted elements and are considered to be "out of order". To correct an inversion, we can swap adjacent elements.
For example, consider . It has two inversions: and . To sort the array, we must perform the following two swaps to correct the inversions:
Given datasets, print the number of inversions that must be swapped to sort each dataset on a new line.
The first line contains an integer, , denoting the number of datasets.
The subsequent lines describe each respective dataset over two lines:
The first line contains an integer, , denoting the number of elements in the dataset.
The second line contains space-separated integers describing the respective values of .
For each of the datasets, print the number of inversions that must be swapped to sort the dataset on a new line.
1 1 1 2 2
2 1 3 1 2
We sort the following datasets:
is already sorted, so there are no inversions for us to correct. Thus, we print on a new line.
As we performed a total of swaps to correct inversions, we print on a new line.