Solving the problem using the merge sort approach (counting inversions while merging subsequences - plus one inversion in a case of element from the left subseq greater than the element from the right) looks feasible (and maybe evident) to implement. But there is one caveat: it is crucial to count not only the one inversion in a case *cur_left > *cur_right, but count elements in a range [cur_left + 1, right_begin) as "inverted" too. That follows from the fact that merged subarrays are sorted in ascending order, so if we encountered the (*cur_left > *cur_right) case, then elements in a range [cur_left + 1, right_begin) satisfies that too and could be counted as inversions.
Hope I stated that clearly.

Edited by author 04.05.2019 18:59

Edited by author 06.05.2019 06:44