Merge Sort

The implementation(generalised ) of merge sort

UVA 10810 Ultra-QuickSort

Basically same as 11495. Just Read question carefully
and read hint related 11495.

uva11495 Bubbles and Buckets

The counting inversion can be done in O(n^2) with the naive algorithm.
But it will not suffice. So we need (nlogn). Counting the inversion in merge function of merge sort is good idea too do this. while merging if second array is having small element then the elements remaning in first array all have conflict with this element so add that and thats it.
or

create binary search tree ,step by step go on inserting the elememnts, and with every node keep track of nodes that are right side of current node and
while inserting increment  the current nodes right count if inserted element falls to right (that is it is greater than current node element).and else if falls to left(that means inserted element is smaller than current node and there are right_count_of_current_node no of element greater than inserted element that are before inserted element so add that count) add right count to answer.

 Solution with first strategy:

HR Red John is back

https://www.hackerrank.com/contests/101july13/challenges/red-john-is-back

Easy solution with the little dp and prime with very mild constraints