Significant Inversions in an array

Question

I'm working on a homework problem to find the number of significant inversions in an array of integers. "Significant inversion" is defined as follows:

A significant inversion in a permutation [a₀, a₁, a₂, ..., a_n] is one in which a_i > 2 a_j for some i < j. so for example a = [4,5,2,1,3] has exactly 3 significant inversions, since for this permutation a₀ > 2 a₃, a₁>2 a₂, a₁ > 2 a₃.

The solution needs to have O(n log n) complexity. This requires the use of a divide and conquer approach. I chose to implement the solution based off of merge sort.

I understand the splitting operation as given here:

def countInversions(list):
    if(len(list) <= 1):
        return list, 0
    else:
        mid = int(len(list)/2)
        left, a = countInversions(list[:mid])
        right, b = countInversions(list[mid:])
        result, c = mergeAndCount(left, right)
        return result, (a + b + c)

However I'm having trouble with the merge and count method. Specifically counting the number of significant inversions. I adapted my code from counting the normal number of inversions.

def mergeAndCount(left, right):
    result = []
    count = 0
    i,j = 0,0
    while(i < len(left) and j < len(right)):
        if(left[i] > 2*right[j]):
            count += 1
        if(left[i] < right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    while(left[i:] or right[j:]):
        if(left[i:]):
            if(left[i] > 2*right[j-1]):
                count += 1
            result.append(left[i])
            i += 1
        if(right[j:]):
            if(left[i-1] > 2*right[j]):
                count += 1
            result.append(right[j])
            j += 1
    return result, count

So print(countInversions([4,5,2,1,3])) should return 3. However, it returns 1.

I'm looking for some guidance on my merge and count method.

---

The final implementation:

def countInversions(list):
    if(len(list) <= 1):
        return list, 0
    else:
        mid = int(len(list)/2)
        left, a = countInversions(list[:mid])
        right, b = countInversions(list[mid:])
        result, c = mergeAndCount(left, right)
        return result, (a + b + c)

def mergeAndCount(left, right):
    result = []
    count = 0
    i,j = 0,0

    while(i < len(left) and j < len(right)):
        if(left[i] > 2*right[j]):
            count += len(left)-i
            j += 1
        else:
            i += 1

    i,j = 0,0
    while(i < len(left) and j < len(right)):
        if(left[i] < right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result, count

Answer 1

You are almost there, but there are two issues:

1. When you have found left[i] > 2*right[i] you are meant to conclude that all of the values in left[i:] are greater than 2*right[i] and so you should increment your count by len(left(i:]) which is the same as len(left)-i. (You are just adding 1 on which is why your values are too low.)

2. You need to split your merge pass into two stages, one to count the significant inversions, and one to produce a sorted output array. (In a normal inversion count, these two would move i and j at the same points so can be combined, but that is not true for your case.)

Fixed code:

def mergeAndCount(left, right):
    result = []
    count = 0
    i,j = 0,0

    while(i < len(left) and j < len(right)):
        if(left[i] > 2*right[j]):
            count += len(left)-i
            j += 1
        else:
            i += 1

    i,j = 0,0                
    while(i < len(left) and j < len(right)):
        if(left[i] < right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    while(left[i:] or right[j:]):
        if(left[i:]):
            result.append(left[i])
            i += 1
        if(right[j:]):
            result.append(right[j])
            j += 1
    return result, count