12.8. Merging and Counting Inversions

So, what we are trying to do is measure the dissimilarity in terms of what we call inversion. How many pairs of movies or rank in the opposite way between you and your friend? So, if you and your friend rank every pair of movies in the same order, then your total order of performances must be the same. So, if there are zero inversions, then you have exactly similar in your taste to your friend and the rankings are identical.

In this chunk, we define what an inversion is. An inversion occurs when two items are ranked differently by two people. For example, if both you and your friend rank movies, and your rankings differ at some points, that's where inversions come into play. If there are no inversions, it means both rankings are identical, indicating that you and your friend have the same taste. Conversely, the more inversions there are, the more different your tastes are. This idea helps to measure how much two people's preferences diverge.

Consider two friends comparing their favorite movies. If both rank 'Inception' higher than 'Titanic,' there are no inversions for those two movies. However, if you rank 'Titanic' higher than 'Inception' while your friend does the opposite, that's an inversion. The more such oppositions you have between the rankings, the more different your tastes become.

On the other hand, if you have n movies, then you can do n choose 2 pairs. So the number of different pairs of movies are n choose 2 which is n into n minus 1 by 2. If every possible movie you disagree with your friend, then the number of inversions will be n into n minus 1 by 2, which is an order n squared.

This chunk explains how to calculate the total number of inversions possible in a list of rankings. If you have 'n' movies, the total possible pairs of different movies you can compare is given by the formula n choose 2, which evaluates to n(n - 1)/2. This means that in the worst-case scenario, where every pair is ranked oppositely by you and your friend, the inversions can reach an order of n squared. Therefore, counting inversions can be computationally intensive as the size of the dataset grows.

Think of a basketball tournament where each game outcome can be rated between two teams. If you have ten match outcomes to look at, you might evaluate each possible pair of games played, which totals to 45 comparisons (10 choose 2). If you and your friend consistently disagree, inspecting all these mismatches can be overwhelming, indicating an exponential increase in the complexity of analysis.

So our whole is to give a more efficient algorithm, so we will move to this divide and conquer paradigm. So, suppose your friend’s permutation, our permutation always 1 to n, so we can just assume it is given.

This chunk introduces the necessity of finding a more efficient way to count inversions rather than brute-force methods, which are quadratic in their complexity. Here, the use of the divide and conquer paradigm is proposed. The idea is to break down the problem into smaller segments, count inversions in those segments, and then efficiently merge the results.

Imagine a teacher grading essays for a class of 100 students. Manually comparing each essay with every other would take forever. Instead, by dividing students into groups, grading each group, and then comparing just the grouped ones can drastically reduce workload and make the grading faster. This is similar to how divide and conquer techniques improve counting inversions.

So, what is the principle of merge and count? So, remember that an inversion across L and R consist of an element in R. So we have an element in R and an element in L, such that this number is smaller than this number..

In this chunk, we describe the merge and count strategy which is essential in counting inversions. During the merge step of sorting, we keep track of any time a smaller number from the right list is placed before a larger number from the left list to identify inversions. Every time we place an element from the right list into our merged result, every unmerged element left in the left list constitutes an inversion, and we count these appropriately.

Consider a line of people arranged by height. If you start seeing shorter people move in front of taller ones, you can count how many taller individuals they go in front of—that's akin to counting inversions! Every time someone shorter steps ahead of a taller person in line, it's a mismatch, just like an inversion with our movie ranking.

--