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.
Furthermore, the description is misleading because the example from the problem description of |2, 1, 3, 1, 2| is an example of isertion sort, not merge sort.
Merge Sort does not swap, but rather divides the array by 2, recursively (O log(n)), and then creates a new array, each divided part is added one at a time with its complement half, in the correct order (O (n)) Total calculation O(n*log(n)), in this way:
After arrays are divided, they are joined like this:
Merge Sort: Counting Inversions
You are viewing a single comment's thread. Return to all comments →
Furthermore, the description is misleading because the example from the problem description of
|2, 1, 3, 1, 2|
is an example of isertion sort, not merge sort.4 steps -> insertion sort
Merge Sort does not swap, but rather divides the array by 2, recursively (O log(n)), and then creates a new array, each divided part is added one at a time with its complement half, in the correct order (O (n)) Total calculation O(n*log(n)), in this way:
After arrays are divided, they are joined like this:
3 steps -> merge sort
Since, this is a merge sort algo, yet, expects the counts to be unrelated to merge sort, I find this to be particularly confusing question.