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 the dataset . 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.
Complete the function countInversions in the editor below. It must return an integer representing the number of inversions required to sort the array.
countInversions has the following parameter(s):
arr: an array of integers to sort .
The first line contains an integer, , the number of datasets.
Each of the next pairs of lines is as follows:
The first line contains an integer, , the number of elements in .
The second line contains space-separated integers, .
For each of the datasets, return the number of inversions that must be swapped to sort the dataset.
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.
We performed a total of swaps to correct inversions.