Problem Detail: The number of possible inversions in an array is bounded by $binom{n}{2}$, i.e $frac{n(n-1)}{2} in O(n^2)$. How it is possible to calculate $O(n^2)$ results in $O(nlog n)$ time using something like modified merge sort? (sample algo : http://www.geeksforgeeks.org/counting-inversions/).
Asked By : basarat
Answered By : Jake
Swaps that make a permutation are different from the number of inversions. A max of $n*log, n$ swaps define a permutation. An inversion in a permutation occurs anywhere one element is less than another element at a higher position so a reverse sorted list has $n^2$ inversions but the corresponding permutation has about $frac{n}{2}$ swaps that define it. We just have to undo the swaps to sort something. If you are familiar with algebra you might look at the symmetric group for more information on this. Specifically a cycle of length 2 is called a transposition and all permutations can be defined by about $n*log,n$ transpositions.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/35175 Ask a Question Download Related Notes/Documents
