Algorithmic Toolbox : Number of Inversions Problem (WEEK 4)

 Number of Inversions


--------------------------------
Problem Introduction An inversion of a sequence 𝑎0, 𝑎1, . . . , 𝑎𝑛−1 is a pair of indices 0 ≤ 𝑖 < 𝑗 < 𝑛 such that 𝑎𝑖 > 𝑎𝑗 . The number of inversions of a sequence in some sense measures how close the sequence is to being sorted. For example, a sorted (in non-descending order) sequence contains no inversions at all, while in a sequence sorted in descending order any two elements constitute an inversion (for a total of 𝑛(𝑛 − 1)/2 inversions). 6 1 5 2 3 Problem Description Task. The goal in this problem is to count the number of inversions of a given sequence. Input Format. The first line contains an integer 𝑛, the next one contains a sequence of integers 𝑎0, 𝑎1, . . . , 𝑎𝑛−1. Constraints. 1 ≤ 𝑛 ≤ 105 , 1 ≤ 𝑎𝑖 ≤ 109 for all 0 ≤ 𝑖 < 𝑛. Output Format. Output the number of inversions in the sequence. Sample 1. Input: 5 2 3 9 2 9 Output: 2 The two inversions here are (1, 3) (𝑎1 = 3 > 2 = 𝑎3) and (2, 3) (𝑎2 = 9 > 2 = 𝑎3). What To Do This problem can be solved by modifying the merge sort algorithm. For this, we change both the Merge and MergeSort procedures as follows: ∙ Merge(𝐵, 𝐶) returns the resulting sorted array and the number of pairs (𝑏, 𝑐) such that 𝑏 ∈ 𝐵, 𝑐 ∈ 𝐶, and 𝑏 > 𝑐; ∙ MergeSort(𝐴) returns a sorted array 𝐴 and the number of inversions in 𝐴.
 
#  Number of Inversions
# Problem Introduction
# An inversion of a sequence 𝑎0, 𝑎1, . . . , 𝑎𝑛−1 is a pair of indices 0 ≤ 𝑖 < 𝑗 < 𝑛 such
# that 𝑎𝑖 > 𝑎𝑗 . The number of inversions of a sequence in some sense measures how
# close the sequence is to being sorted. For example, a sorted (in non-descending
# order) sequence contains no inversions at all, while in a sequence sorted in 
#descending order any two elements constitute an inversion (for a total of 𝑛(𝑛 − 1)/2
# inversions).
# 6 1 5 2 3
# Problem Description
# Task. The goal in this problem is to count the number of inversions of a given sequence.
# Input Format. The first line contains an integer 𝑛, the next one contains a sequence of integers
# 𝑎0, 𝑎1, . . . , 𝑎𝑛−1.
# Constraints. 1 ≤ 𝑛 ≤ 105
# , 1 ≤ 𝑎𝑖 ≤ 109
# for all 0 ≤ 𝑖 < 𝑛.
# Output Format. Output the number of inversions in the sequence.
# Sample 1.
# Input:
# 5
# 2 3 9 2 9
# Output:
# 2
# The two inversions here are (1, 3) (𝑎1 = 3 > 2 = 𝑎3) and (2, 3) (𝑎2 = 9 > 2 = 𝑎3).
# What To Do
# This problem can be solved by modifying the merge sort algorithm. For this, we change both the Merge and
# MergeSort procedures as follows:
# ∙ Merge(𝐵, 𝐶) returns the resulting sorted array and the number of pairs (𝑏, 𝑐) such that 𝑏 ∈ 𝐵, 𝑐 ∈ 𝐶,
# and 𝑏 > 𝑐;
# ∙ MergeSort(𝐴) returns a sorted array 𝐴 and the number of inversions in 𝐴.

#-----------solution---------------
def merge(leftright):
    i, j, count_inv = 000
    latest = list()
    while i < len(left) and j< len(right):
        if left[i] <= right[j]:
            latest.append(left[i])
            i += 1
        else:
            latest.append(right[j])
            count_inv += len(left) - i
            j += 1

    latest += left[i:]
    latest += right[j:]
        
    return latest, count_inv

def merge_sort(arr):
    global count_total
    if len(arr) <= 1:
        return arr
    mid = len(arr)//2

    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    sorted_arr, temp = merge(left, right)
    count_total += temp

    return sorted_arr

count_total = 0
n = int(input())
seq = [int(i) for i in input().split()]
merge_sort(seq)
print(count_total)




---------------------------------