CODEWITHSUNDEEP
algorithmmergesortdivide-and-conquerinversion
Andrew Tobey
Andrew Tobey

Reputation: 923

refine merge-sort to count number of inversions

I'm working on an improved version of merge sort so that it counts the number of inversions.

Note: I don't want you to get my homework done, but I have some ideas about this and would love to know whether they make sense at all.

As merge-sort is O(nlogn I need to adjust it without worsing its overall performance. I think to this I have to insert a test that takes constant time (1)

(1) I test for inversion (upper) with A[i] > A[j] given that i<j

To find the appropriate spot to insert the test I am asking myself: when during the execution of merge sort is guaranteed that the test runs unrelated to n?

I think the only spot where this is true is when the list is split into one-element lists

Hence, I would propose the following algorithm adjustment 

use divide-and-conquer and split the list to one elements lists
test A[i] > A[j] as i<j is true for two adjacent lists

Does this make sense at all?

Eventually, I have to carry with the count of inversions until the algorithm terminates. Could someone give me a hint with regard to this problem?

(Intuitively I would give the count to the merge part as the algorithm terminates when merging is complete.)

Cheers, Andrew

Upvotes: 1

Views: 387

Answers (1)

Jordi Vermeulen
Jordi Vermeulen

Reputation: 1198

If you only count when the array size is 1, you're only looking at pair-wise inversions. I think you just want to keep a counter throughout all the recursive calls, and increment it whenever, during the merge step, you compare an element from the left subarray to one from the right subarray and the one from the right is smaller (assuming you're sorting in ascending order).

Upvotes: 1

Related Questions