Количество элементов 10^5 обычно подразумевает, что решение за квадрат не пройдёт, а вот O(nlogn) - устроит.
Для достижения такой сложности можно использовать сортировку слиянием. В процедуре слияния (merge) есть такой шаг, когда в результат пишется элемент из правой половины. Вот в этот момент нужно к (локальному) счётчику инверсий добавить количество ещё неиспользованных элементов левой половины.
invcount = 0
...
if left[i] <= right[j]:
a[k] = left[i]
i += 1
k += 1
else:
a[k] = right[j]
invcount += length(left) - i
j += 1
k += 1
...
return invcount
А в рекурсивной процедуре mergesort нужно сложить количество инверсий в левой половине, количество в правой, и количество инверсий, возникающих при слиянии (то, что возвращает merge)
... разделение массива на две части
return mergesort(left) + mergesort(right) + merge(left, right)
вот этот код прошёл
Этот же код у Вас был с самого начала, и он не должен проходить при n=100000