Count greater elements to the left of an element in array in C++ (using Merge Sort)

  c++, mergesort, sorting

Recently I came across a problem on C++, where I had to take an array as input with a number of testcases to be given as input, and I had to print the number of elements(corresponding to each element of the array) which were greater than that element and solely to the left of that element! Since I had to work with huge data constraints, O(n^2) was a bad choice. So I thought of using merge sort for the same to bring down the complexity to O(nlogn). But I’m facing some difficulty in doing so, like I can’t position the pointers such that whenever a greater element to the left is found, it’s count is increased by 1 each time it has to go right from left. Can someone implement merge sort to solve the above problem and provide some explanation as well?(I’m just a rookie in CP!)

Source: Windows Questions C++

LEAVE A COMMENT