CODEWITHSUNDEEP
arraysalgorithmsortingrecursionmergesort
pi2018
pi2018

Reputation: 357

Inversions in the array, what am I getting wrong. Please have a look at the Math/Pseudo code below

I have been trying to write a pseudo code for the number of inversions.

For this illustration let our array be called mainArray of length n. and also assume that n is an even integer.

From my understanding an inversion in an array is needed when i<j, mainArray[i] > mainArray[j]. We then swap places in order to sort this.

Using the merge sort algorithm, once we reach the base case and start merging the two halves (left-half and right-half) the code looks like the following

let i = 0, j=0, k=0, inversions = 0
for k in range(0,n-1) 
    if left-half[i] < right-half[j]
       mainArray[k] = left-half[i]
       i+=1
    else
       mainArray[k] = right-half[j]
       j+=1

       //now at this point an inversion has occurred
       //so from my understanding at this point there was only 1 swap? because the program 
       //skipped left-half[i] and proceeded to right-half[j]
       // so my answer was **"Inversions = Inversions + 1"** incrementing by 1 Inversions wherever the **Else-Block is run**. 


       //but in the solution the correct answer is 
       Inversions = Inversions + {(n/2)-i}

I don't get this part? why are assuming that the right-half[j] swaps places with all the remaining elements in the left-half of the array. what key-point am I missing here?

Any help would be appreciated. Thanks.

Upvotes: 0

Views: 56

Answers (1)

David G
David G

Reputation: 96810

Recall that left-half and right-half is sorted, so if i<j, left-half[i] > right-half[j] this implies left-half[i+1..n/2] > right[j] too. So we count Inversions + {(n/2)-i} to count all of the inversions, not just one.

Upvotes: 2

Related Questions