Inversion Counting Problem or Another reference

• Status: Completed

Algorithm	Solved	Solution	Time
Merge Sort		Sol	0.15
Fenwick Tree		Sol	?

Solution description

The complete solution use the merge sort to count the number of inversion count, the basic idea the merge sort use the invention technique to sort the array, and in this solution, we count the number of inversions that the merge sort need to sort the array.

The time complexity is O(N log N) and the space complexity is O(N log N) because we need to use the tree to make the remapping of the input.