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.
- Merge Sort: Counting Inversions
- Discussions
Merge Sort: Counting Inversions
Merge Sort: Counting Inversions
Sort by
recency
|
505 Discussions
|
Please Login in order to post a comment
C++ solution. Solving this by merge sort is probably the quickest way, as it is done in O(nlogn) time, as opposed to other methods most of which run in O(n^2).
An addition to the merge sort algorithm made specifically for this question is that we need to keep track of the number of swaps made in the algorithm.
For people looking for PHP solution. You can use the merge sort procedure to solve this
Python3 My Solution
JavaScript:
If you're confused about the reason why it's still
timeout
with the usage of merge sort, you can consider to turn the creation of the helper vector to a reference in the parameter list of merge sort funtion to reduce the time spent on creation.