условие задачи:

Число инверсий

Имя входного файла: inversions.in
Имя выходного файла: inversions.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

Инверсией в последовательности чисел A называется такая ситуация, когда i < j, а Ai > Aj.
Дан массив целых чисел. Ваша задача — подсчитать число инверсий в нем.
Подсказка: чтобы сделать это быстрее, можно воспользоваться модификацией сортировки слиянием.

Формат входного файла
В первой строке входного файла содержится число n (1<n<100 000) — число элементов в массиве. Во второй строке находятся n целых чисел, по модулю не превосходящих 109.

Формат выходного файла
В выходной файл надо вывести число инверсий в массиве.

Пример
inversions.in
inversions.out
10
1 8 2 1 4 7 3 2 3 6

17
моё решение задачи на github:
https://github.com/fizitra/OpenEdu_ITMO_Algorithms/blob/master/Week2_Comarisons_sort/week2_problem3_inversions.py

однако есть проблема: превышение предела времени работы программы на 7 тесте
https://courses.openedu.ru/courses/course-v1:ITMOUniversity+PADS+fall_2016/courseware/a59fe37ef4744951ab33fa6278dd20f9/70393a1a9f654ce88dfec1291933e75e/

Прошу помощи. Как еще можно ускорить код на питоне?!

Проблема решена.
Если кому интересно, то вычисление длины списка len выполняется за линейное время. Заменил все len на константу в итоге прирост скорости в 18-25 раза.
Поскольку публиковать свои решения в сети пока идет курс не этично, окончательного варианта решения здесь не привожу, если кому очень нужно, найдет сам.

fizitra
у всех стандартных типов данных len берется за O(1)
срезы медленные, доступ к глобальным переменным медленный, создание нового list и append к нему медленные

sander
fizitraу всех стандартных типов данных len берется за O(1)срезы медленные, доступ к глобальным переменным медленный, создание нового list и append к нему медленные

Да моя оплошность, пожалуй вы правы len за О(1) вся проблема была в самих срезах. Правда пока не ясно как, потому что формируемый в коде срез из len(list)//2 остался, и сохраняется какновый list. Этот новый list использовался для нахождения нового значения len(list). В новом варианте алгоритм работает запоминая начальное значение первого len(list), и дальше остальные значения вычисляются как const//2.
Т.е в некотором роде вопрос открыт: в каком месте происходит потеря времени в алгоритме?

fizitra
Подсказка: чтобы сделать это быстрее, можно воспользоваться модификацией сортировки слиянием.

Чтобы выполнять сортировку слиянием, нужно знать длину массива. Хорошо, когда длина есть, а если её нет? Так бывает гораздо чаще в реальной жизни. Поэтому если хочешь чему-нибудь научиться, нужно подумать, как сделать это, не учитывая известную длину, а работая лишь с поступающими числами, пока они не закончатся.

Естественно, квадратный вариант будет слишком долгим (когда для каждого элемента перебирается всё справа), но есть линейный вариант (однопроходный), требующий немного дополнительной памяти.