6. An inversion in an array A1...n is a pair of indices (i, j) such that i < j and A; > Aj. The number of inversions in an n-element array is between 0 (if the array is sorted) and (2) (if the array does not have equal values and is sorted backward). Design an algorithm to count the number of inversions in an n-element array in O(n log n) time. Establish the correctness and analyze the running time of your algorithm. Hint. You may want to modify MERGESORT.
6. An inversion in an array A1...n is a pair of indices (i, j) such that i < j and A; > Aj. The number of inversions in an n-element array is between 0 (if the array is sorted) and (2) (if the array does not have equal values and is sorted backward). Design an algorithm to count the number of inversions in an n-element array in O(n log n) time. Establish the correctness and analyze the running time of your algorithm. Hint. You may want to modify MERGESORT.
Related questions
Question
question 6
Transcribed Image Text:6. An inversion in an array A1...n is a pair of indices (i, j) such that i < j and A; > Aj. The
number of inversions in an n-element array is between 0 (if the array is sorted) and (2) (if the
array does not have equal values and is sorted backward). Design an algorithm to count the
number of inversions in an n-element array in O(n log n) time. Establish the correctness and
analyze the running time of your algorithm.
Hint. You may want to modify MERGESORT.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
