Which approach counts inversions (pairs i a[j]) in O(n log n)?

Merge sort, counting left elements each right one passes

Counting sort followed by a single linear pass

Two nested loops with an early exit when sorted

Algorithms and Data Structures · Senior · Question 69 of 75

Which approach counts inversions (pairs i < j with a[i] > a[j]) in O(n log n)?

1Counting sort followed by a single linear pass
2Two nested loops with an early exit when sorted
✓Correct answer: Merge sort, counting left elements each right one passes

Explanation

When an element from the right half is merged before the remaining left elements, it forms an inversion with each of them. A Fenwick tree over values also works in O(n log n).

Which approach counts inversions (pairs i < j with a[i] > a[j]) in O(n log n)?

Explanation

Further reading

Problem with a question

Test yourself

Feedback