Алгоритмы. Инверсии в массиве

Количество инверсий в массиве показывает, насколько это массив "хорошо" отсортирован. 

Что такое инверсия? Пара элементов A[i] и A[j] являются инверсией, если A[i] > A[j] и i < j. Массив [2, 4, 1, 3, 5] содержит три инверсии (2, 1), (4, 1), (4, 3). Максимальное количество инверсий в массиве из n элементов – (n*(n-1))/2.  Если в массиве инверсий нет, то массив полностью отсортирован. 

Зачем это считать? Например, вы решили узнать насколько у вас и вашей девушки схожие вкусы в выборе фильмов. Сделали список из 10 фильмов, которые и вы и она смотрели. Затем каждый для себя расположил эти фильмы в порядке от наиболее понравившегося к наименее. По одному из ваших списков отсортировали второй и посчитали количество инверсий. В итоге, если инверсии нет, то ваши вкусы идеально совпадают, а если их 45, то на вопрос "Что будем смотреть?", вы вряд ли найдёте быстрый ответ.