12.9. Implementation of Merge Procedure with Counting

So, what we are trying to do is measure the dissimilarity in terms of what we call inversion. How many pairs of movies are ranked in the opposite way between you and your friend? 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. 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...

In this chunk, we learn that 'inversions' are used to compare rankings between two individuals. If both individuals rank movies the same way, they have zero inversions, meaning their preferences align perfectly. If they disagree on their rankings, each disagreement is counted as an inversion. The total number of pairs of movies ranked, or inversions, is calculated with the formula n choose 2, which mathematically represents the potential disagreement pairs.

Imagine two friends who watch the same five movies. If they both agree that Movie A is the best and Movie E is the worst, and only disagree on the rankings of Movies B, C, and D, each disagreement (inversion) counts towards their overall similarity. The fewer inversions they have, the more aligned their tastes are.

So, our whole aim is to give a more efficient algorithm, so we will move to this divide and conquer paradigm. Suppose your friend’s permutation, our permutation always 1 to n... To solve this efficiently, we will count inversions while sorting these segments and using a merge procedure.

This chunk introduces the concept of using a divide-and-conquer strategy, particularly merge sort, to count inversions in an efficient manner. Instead of examining every single pair of rankings to count inversions (which would be slow), the merge sort algorithm helps break the problem into smaller pieces, counts inversions within these pieces, and combines these counts as it merges the sorted lists back together.

Think of organizing five books by size using a sorting method. Instead of comparing every book with every other book individually, you can split them into smaller piles, sort each pile, and then combine the sorted piles while noting the order changes (inversions) that show how the books got rearranged.

So, how do we do this? So, what is the principle of merge and count? So, remember that an inversion across L and R consists of an element in R... So, any time now if I had pulled out an element from here; that means, at this current pointer I have merged up to this and up to this...

In this chunk, we learn about the process of merging sorted arrays while simultaneously counting inversions. The idea is that if an element from the right list is smaller than an element from the left list, this indicates that there are inversions equal to the number of remaining elements in the left list. This is because that right element is out of place compared to those left elements which are larger. This way, inversions are counted dynamically during the merging process.

Imagine you are building a line of dominoes where some are taller (right list) and others shorter (left list). If you set up a taller domino in line before a shorter one, each shorter domino that comes after creates an inversion as it should have been set before the taller ones! This is how the count of inversions grows as you merge the two styles together.

So, now we incorporate our merge procedure into the merge sort with counting as follows... our total number of inversions is the count from the left and the right count from the merge together and the new array is the one returned by the merge.

This final chunk elaborates on how the two processes—counting inversions and sorting—are combined using the merge sort algorithm. As the left and right sections are recursively sorted and counted, their counts are combined during the merge step, resulting in a streamlined method for obtaining both sorted data and inversion counts efficiently.

Think of a synchronized event like a dance performance where two groups (left and right) come together on stage. Each group practices their order separately but during the final performance, they incorporate and count how many times a dancer from one group out of sync with a dancer from another group. This way they produce a beautiful performance while keeping track of missteps (inversions) all at once!

--