Count number of inversions

Given an unsorted array, count the number of inversions.

Solution

• Use the merge sort algorithm and enhance it with the inversion count
• In the merging step, count inversions
  • if value in a > value in b, then inversions = a.end - a_index
• Repeat this until the entire array is merged

Code

def count_inversions(arr)
    merge_sort(arr, 0, arr.size)
end

def merge_sort(arr, left, right)
    return 0 if left >= right
    mid = (left + right) / 2
    inversions = 0
    inversions += merge_sort(arr, 0, mid)
    inversions += merge_sort(arr, mid, right)
    inversions += merge(arr, left, mid, right)
    return inversions
end

def merge(arr, first, second, end)
    temp = []
    inversions = 0 
    i = first
    j = second

    while i < second && j < end
        if arr[i] <= arr[j]
            temp << arr[i]
            i += 1
        else
            temp << arr[j]
            inversions += second - i
            j += 1
        end

    end

    i = first
    j = 0
    while i < end
        arr[i] = temp[j]
        i += 1
    end

    return inversions
end

Time complexity

O(n log n) for merge sort