algorithm - Count number of inversions in an array (python code)

Question

So I'm reading through this code, it's going through a file containing 10,000 integers in some random order(no repetition), and counting the number of inversions. I'm not understanding this code fully, I have couple questions: First I suppose this is keep breaking the array into left and right, until the length is 1. When both left array and right array have length 1, what do we do and count here?(I might be completely misunderstanding this code please correct me). And where does the "midsection" element go each time? From what I see every time this element does not belong to either the right or the left array. Last question is that the line "count += (len(a)-i)" is correct only if both the left and right array are sorted(ordered) already, but I do not see where this sorting process is. Here is the code:

from pathlib import Path
file_path = Path("c:/Users/Lyra/Desktop/Algorithm/")

inFile = open(file_path / "IntegerArray.txt", 'r')

with inFile as f:
    numList = [int(integers.strip()) for integers in f.readlines()]
    
count = 0

def inversionsCount(x):
    global count
    midsection = len(x) // 2
    leftArray = x[:midsection]
    rightArray = x[midsection:]
    if len(x) > 1:
        # Divid and conquer with recursive calls
        # to left and right arrays similar to
        # merge sort algorithm
        inversionsCount(leftArray)
        inversionsCount(rightArray)
        
        # Merge sorted sub-arrays and keep
        # count of split inversions
        i, j = 0, 0
        a = leftArray; b = rightArray
        for k in range(len(a) + len(b) + 1):
            if a[i] <= b[j]:
                x[k] = a[i]
                i += 1
                if i == len(a) and j != len(b):
                    while j != len(b):
                        k +=1
                        x[k] = b[j]
                        j += 1
                    break
            elif a[i] > b[j]:
                x[k] = b[j]
                count += (len(a) - i)
                j += 1
                if j == len(b) and i != len(a):
                    while i != len(a):
                        k+= 1
                        x[k] = a[i]
                        i += 1                    
                    break   
    return x
# call function and output number of inversions
inversionsCount(numList)
print (count)

I know I've asked a lot question but I'm really confused right now, and thanks in advance!

question from:https://stackoverflow.com/questions/65641474/count-number-of-inversions-in-an-array-python-code

Answer 1

There is no "midsection" element. midsection is just an index in the middle of x leftArray = x[:midsection] and rightArray = x[midsection:] will together copy all elements in x and if length is odd the middle element will end up in rightArray.

The sorting is made by the function itself by altering the elements in the passed argument x. A list is mutable and passed to the function as a reference. So every x[n] = something is affecting the passed list argument and therefore also affecting corresponding variable in the calling scope. That means after inversionsCount(leftArray) leftArray is sorted.

If you run a smaller list like inversionsCount([6,0,3,1,2,5,4]) and put in some print(interesting_varable) in the code. Then you may find out what happens.