Search code examples
arraysinversion

inversion pairs in an array - application

I came across an algorithmic problem to find out the number of inversion pairs in an array in O(nlogn) time. I got the solution to this. But, my question is that what is the real-life application of this problem? Like I want to know some applications where we need to know the inversion pairs.

Solution

  • One example is the fifteen puzzle. If you want to randomly shuffle a grid of numbers, can you tell at a glance if

    1 14  5  _
7  3  2 12
6  9 13 15
4 10  8 11

    can be solved by sliding moves or not? The parity of the permutation will tell you that it is not.