We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
A merge sort is useful because: 1) it is faster than a bubble sort, but 2) if you did perform the merge sort by swapping adjacent elements rather than copying to a second array, you would never swap any adjacent elements that weren't inverted. A merge sort, thus modified, would use the same number of swaps as a bubble sort that avoided non-inverted swaps by bringing down elements in ascending order (say, by using a map).
The key to the problem is that it is easy to perform an actual (and therefore fast) merge sort while calculating how many swaps you would have done to get each transformation.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Merge Sort: Counting Inversions
You are viewing a single comment's thread. Return to all comments →
A merge sort is useful because: 1) it is faster than a bubble sort, but 2) if you did perform the merge sort by swapping adjacent elements rather than copying to a second array, you would never swap any adjacent elements that weren't inverted. A merge sort, thus modified, would use the same number of swaps as a bubble sort that avoided non-inverted swaps by bringing down elements in ascending order (say, by using a map).
The key to the problem is that it is easy to perform an actual (and therefore fast) merge sort while calculating how many swaps you would have done to get each transformation.