2.6 - Counting Inversions in an Array in O(n log n) time via Divide and Conquer

Given an array A[1,n] of numbers, we need to count the number of inversions.
As inversion is a pair of positions (i, j), such that i is smaller than j, but i-th element is larger than j-th element (i.e, the elements are out of order with respect to sorted order). This can be solved in O(n log n) time via a Divide and Conquer algorithm.

[@javeriyanadaf9314]

Beautifully put together

[@elirhm5926]

the best explaination ever! thank you so much!

[@user-gu5bk1og7c]

some solid work out there

[@carlavn2470]

Shouldn't the counter at 8 be 4?

[@algorithmsbysharmathankach7521]

I was counting in the other direction --- i.e.,for each number, how many are on its RIGHT side that are smaller.

[@carlavn2470]

@@algorithmsbysharmathankach7521 right, I get that. But if we are using the R side as a counter, shouldn't the count change to 4 instead of staying as 3 at digit 8?

[@algorithmsbysharmathankach7521]

@@carlavn2470 didn't get it, can you tell me where exactly (time in the video) is the mistake?

[@carlavn2470]

@@algorithmsbysharmathankach7521 at min 17:48

[@algorithmsbysharmathankach7521]

@@carlavn2470 yes, it is 4 (my bad) -- thankyou!