Swapping Ints

The problem is basically asking for the list inversion. That is the pair of elements $(i,j)$ in $A[0......n]$ such that $i<j$ and $A[i]>A[j]$ .

Just like the maximum sub-array problem we use a divide and conquer approach, An inversion $i,j$ can occur in the left half, right half and $i$ on the left half and $j$ on the right half. We implement a modified merge-sort algorithm which in addition to sorting also counts the number of inversion. First lets implement a merge subroutine to count the number of inversion between the left and right sorted sub-arrays. For every element in the left sub-array(left[i]) we look for an element in the right sub-arrays(right[i]) that is strictly smaller than left[i].

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def merge_cross(left, right):
    result = []
    i, j, inversion = 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            inversion += j #when we insert left[i] into the result we know every element to the left of j is less than left[i]
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    inversion += j*(len(left)-i)
    result += left[i:]
    result += right[j:]
    return inversion, result

With the merge procedure at hand we can write a divide and conquer algorithm Base case: return $0$ if the number of elements is equal to one else: recur on the left and right half

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def count_inversion(A):
    return merge_sort(A)[1]

def merge_sort(A):
    if len(A) <= 1:
        return 0, A
    middle = len(A)/2
    left_inversions, left = merge_sort(A[:middle])
    right_inversions, right = merge_sort(A[middle:])
    merge_inversions, merged = merge(left, right)
    inversions = left_inversions + right_inversions + merge_inversions
    return inversions, merged

The algorithm runs in $O(nlogn)$ .