Разделяй и властвуй: подсчет количества инверсий в массиве

Есть функция для подсчета инверсий в массиве, требующая О(n2) времени:
static void Inverses(int[] A, ref int count) { count = 0; for(int i = 0; i < A.Length - 1; i++) { for (int j = i + 1; j < A.Length; j++) { if( A[i] > A[j] ) count++; } } }
Также есть функция сортировки массива подходом разделяй и властвуй, требующая O(n*log(n)) времени:
static Int32[] Merge_Sort(Int32[] massive) { if (massive.Length == 1) return massive; Int32 mid_point = massive.Length / 2; return Merge(Merge_Sort(massive.Take(mid_point).ToArray()), Merge_Sort(massive.Skip(mid_point).ToArray())); }
static Int32[] Merge(Int32[] mass1, Int32[] mass2) { Int32 a = 0, b = 0; Int32[] merged = new int[mass1.Length + mass2.Length]; for (Int32 i = 0; i < mass1.Length + mass2.Length; i++) { if (b < mass2.Length && a < mass1.Length) if (mass1[a] > mass2[b]) merged[i] = mass2[b++]; else //if int go for merged[i] = mass1[a++]; else if (b < mass2.Length) merged[i] = mass2[b++]; else merged[i] = mass1[a++]; } return merged; }
Нужно реализовать алгоритм подсчета инверсий в массиве с подходом разделяй и властвуй, которому требовалось бы O(n*log(n)) времени.
К сожалению, мне достаточно тяжело дается понимание рекурсии, когда первый метод вызывает другой метод, а другой вызывает первый при условии.

Ответ

Вам сначала нужно разобраться с сортировкой слиянием, а именно понять идею алгоритма, а потом уже разбираться с инверсией.
Скажу кратко: мы разбиваем массив на две части, каждую из этих частей, в свою очередь, тоже разбиваем на две части и т.д., пока наши части не будут состоять из одного элемента. После разбиения мы сливаем парами части в одну так, чтобы результирующая часть была отсортирована - сравниваем элементы одной части с элементами другой соответственно и записываем их в нужном порядке в результирующую. Затем полученные части мы опять попарно сольем и т.д., пока у нас не останется одна часть, которая и будет являться отсортированным массивом.
Текстом трудно понять, поэтому рекомендую посмотреть графическую демонстрацию (на той же википедии есть гифка). Когда поймете идею, уже можно вникать и в реализацию.
Насчет инверсий
Когда мы сливаем обе части, как я уже говорил, мы сравниваем элементы одной (первой, левой) части с элементами другой (правой, второй) части соответственно. И если элемент левой части больше элемента правой части соответственно, то значит это и есть инверсия. И так же все оставшиеся элементы левой части тоже будут больше, т.к. левая и правая часть отсортированы. Поэтому количество инверсий нужно увеличить на количество оставшихся элементов + 1 (текущий элемент).
UPD:
Вот и пример.
Индексация идет с 0. Не описывал, что добавляем элементы в результирующую часть, думаю, это и так понятно. Описал только те части, в которых есть инверсии. Возможны ошибки, т.к. быстро делал. Да и пришлось так сжато уместить элементы, чтобы картинка полностью отобразилась на хэшкоде.