12.6. Brute Force Approach to Count 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.

An inversion is a situation where two items are ranked differently by two individuals. For example, if one person ranks a movie A higher than movie B, but another person ranks movie B higher than movie A, then this pair represents an inversion. If there are no inversions, it means both individuals have exactly the same ranking order.

Think of it like two friends discussing their favorite movies. If both say the same movie is the best and agree on the order of their favorites, they have zero inversions. But if one friend thinks a particular movie is terrible, while the other thinks it's great, that disagreement shows an inversion.

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. So, what is early interesting is our friends permutation, so the friends permutation is some order of 1 to n jumbled up, let us call it i 1 to i n.

The brute force method for counting inversions involves checking every possible pair of items to see if they are inversions or not. This leads to a computational complexity of O(n²), meaning that if there are n items, the method will take time proportional to n squared. Essentially, for each item, you compare it with every other item and count how many pairs are inverted.

Imagine sorting a deck of cards by checking each card against every other card to see which one should be placed in front. This is how the brute force method works: it exhaustively checks every possible combination, just like someone sifting through 52 cards to determine their appropriate order.

So, how do we do this? 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.

The merge and count strategy improves efficiency by combining the counting of inversions with the merge step of the merge sort algorithm. Instead of checking all pairs, as you merge two sorted arrays, you count how many times an element from the right array is less than an element from the left array. This counts inversions while sorting, leading to a time complexity of O(n log n).

Think of a race where two friends are running. As they cross the finish line, each time one friend beats the other, you note down 'inversion.' Instead of reporting every position they ran, you only track who finished before whom as they pass you. This is efficient and gives you the necessary information about their performance (like counting inversions) without having to look at every earlier position.

Now, we incorporate our merge procedure into the merge sort with counting as follows. As usual, we will sort in general an array from some left index to some right index, because we would sort different segments and different times.

With the merge sort technique now enhanced to count inversions, we can recursively sort segments of the array, count inversions within each segment, and count during the merge step. This method is efficient and aesthetically elegant, reducing what was initially a potentially O(n²) operation to O(n log n).

For a final analogy, think of a teacher who grades tests. Instead of looking at each answer and checking individually, the teacher grades the tests in chunks while also noting how many students missed questions that were answered correctly by others. This is like merging and counting inversions efficiently!

--