Алгоритм подсчета инверсий без использования сортировки слиянием (c ++)

В течение нескольких дней я пытался придумать код, следующий за псевдокодом ниже, чтобы подсчитать количество инверсий в несортированном списке чисел перестановок. Мне нужно, чтобы алгоритм работал за O (nlogn), но я могу думать только о решении за O (n ^ 2logn).

Более конкретно, я хотел бы знать, как ускорить 2-й шаг, не используя вложенный цикл for. Я знаю, что есть другие эффективные алгоритмы (например, сортировка слиянием), которые будут работать, но мне нужно следовать шагам псевдо-кода.

Instance: An array A[1] . . . A[n], a permutation of n numbers 1, . . . , n
Question: Calculate vector B[j] = |{A[i] : j > i and A[i] > A[j]}| (the same as
B[j] = |{i : j > i and A[i] > A[j]}|) B[j] is the number of element
larger than A[j] to the left of A[j] in t the array A. In other words,
the sum of the elements in B is equal to the number of inversions in
the permutation A[1] . . . A[n].
(1) Initialize B[i] to 0.
(2) For each even A[j] find elements with indices smaller than j that are by one larger
than A[j]: increase B[j] by the number of such elements;
(3) Divide each A[i] by 2 (in the integer sense);
(4) Stop when all A[i] are 0.

Вот код, который я придумал:

long long numInversions = 0;
// number of elements that are zero in the array
unsigned int zeros = 0;

do {

// solution will need to replace this nested
// for loop so it is O(n) not O(n^2)
for (int i = 0; i < permNumber; i++){

// checks if element is even
if(array[i] % 2 == 0){
for (int j = i; j >= 0; j--){
if (array[j] == array[i] + 1){
numInversions++;
}
}
}

}

// resets value of zeros for each pass
zeros = 0;

for (int k = 0; k < permNumber; k++){
array[k] = array[k] / 2;
if (array[k] == 0)
zeros++;}

} while(zeros != permNumber);

Примечание: алгоритм должен возвращать количество инверсий в списке, скаляр. Псевдокод запрашивает массив, но в конце элементы массива суммируются для вычисления количества инверсий.

Example: Consider a permutation (2, 3, 6, 1, 3, 5) with six inversions. The
above algorithm works as follows:
2 4 6 1 3 5        (no pairs)                                  ÷2
1 2 3 0 1 2 1 =    0: one '1' to left, 2: one 3 to left        ÷2
0 1 1 0 0 1 1 =    0: two '1's to left, 0: two '1's to left    ÷2
0 0 0 0 0 0        total: 6 pairs