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.
Check: Week 1, O(n log n) Algorithm for Counting Inversions I, II
We can avoid allocating and copying multiple arrays by using a single aux array of size n (where n is the size of the original array). Both arrays are switched on each recursive call.
Merge Sort: Counting Inversions
You are viewing a single comment's thread. Return to all comments →
A great explanation by Tim Roughgarden can be found on Coursera: https://www.coursera.org/learn/algorithm-design-analysis
Check: Week 1, O(n log n) Algorithm for Counting Inversions I, II
We can avoid allocating and copying multiple arrays by using a single
aux
array of sizen
(wheren
is the size of the original array). Both arrays are switched on each recursive call.