====== 5.3 Counting Inversions ======
\\
Counting inversions is a problem that we face when analyzing rankings in several applications. The main challenge in this category of problems is to find a way to efficiently compare the rankings.\\
Let's suppose we have a sequence of n numbers a<sub>1</sub>,a<sub>2</sub>,a<sub>3</sub>,...,a<sub>n</sub>, assuming that all the numbers are different. Our concern is to find a measure that tells us how far this sequence is from being in ascending order. The value of that measure should be 0 if the list is sorted and should increase as the list gets more scrambled. Two indices i<j are inverted if a<sub>i</sub> > a<sub>j</sub>j, this means that a<sub>i</sub> appears after a<sub>j</sub> even though i<j.\\
\\
=====  Designing and Analyzing the Algorithm =====

Looking at every pair of numbers would take us O(n²) time.Our aim is to solve the problem in O(nlogn) time.So the algorithm we choose can not look at each inversion individually. \\
\\
Algorithm
Divide the problem into two lists
>>>>>>>>>>>>>>>>>>>>>>>> Merge-and-Count(A,B):
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Maintain a //current// pointer into each list, initialized to point to the front elements\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Maintain a variable //count// for the number of inversions,initialized to 0\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> While both lists are not empty:\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Let a<sub>i</sub> and b<sub>j</sub> be the elements pointed to by the //current// pointer.\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Append the smaller of the 2 elements above to the output list\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> If b<sub>j</sub> is the smaller element:\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Increment //Count// by the number of elements remaining in A.\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> End if\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Advance the //current// pointer in the list from which the smaller element was selected.\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> End While\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Once one list is empty, append the remainder of the list to the output\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Return //Count// and the merged list.\\
\\
The total running time of this algorithm is O(n) time.For solving the problem,we simultaneously sort and count as follows:\\
\\
>>>>>>>>>>>>>>>>>>Sort-and-Count(L)\\
>>>>>>>>>>>>>>>>>>>>>>>> if list L has one element\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>return 0 and the list L\\
>>>>>>>>>>>>>>>>>>>>>>>> Divide the list into two halves A and B\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> (i<sub>A</sub>, A) = Sort-and-Count(A)\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> (i<sub>B</sub>, B) = Sort-and-Count(B)\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> (i, L) = Merge-and-Count(A, B)\\
>>>>>>>>>>>>>>>>>>>>>>>>> return i = i<sub>A</sub> + i<sub>B</sub> + i and the sorted list L\\
\\
For a list with n elements, the overall running time is O(nlogn). \\
I give this section 8/10