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.
If I understand this correctly, the merge sort is needed to complete the sorting without timing out. In fact, a merge sort cannot technically be used to perform the sorting demanded by the problem, since a merge sort does not swap adjacent elements. In the course of performing a merge swap, however, it is not difficult to calculate the number of such swaps that would be needed to achieve each transformation of the array.
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 →
If I understand this correctly, the merge sort is needed to complete the sorting without timing out. In fact, a merge sort cannot technically be used to perform the sorting demanded by the problem, since a merge sort does not swap adjacent elements. In the course of performing a merge swap, however, it is not difficult to calculate the number of such swaps that would be needed to achieve each transformation of the array.