Использование Mergesort для вычисления числа инверсий в C++

Question

void MergeSort(int A[], int n, int B[], int C[]) 
{ 
    if(n > 1) 
    { 
     Copy(A,0,floor(n/2),B,0,floor(n/2)); 
     Copy(A,floor(n/2),n-1,C,0,floor(n/2)-1); 
     MergeSort(B,floor(n/2),B,C); 
     MergeSort(C,floor(n/2),B,C); 
     Merge(A,B,0,floor(n/2),C,0,floor(n/2)-1); 
    } 
}; 

void Copy(int A[], int startIndexA, int endIndexA, int B[], int startIndexB, int endIndexB) 
{ 
    while(startIndexA < endIndexA && startIndexB < endIndexB) 
    { 
     B[startIndexB]=A[startIndexA]; 
     startIndexA++; 
     startIndexB++; 
    } 
}; 

void Merge(int A[], int B[],int leftp, int rightp, int C[], int leftq, int rightq) 
//Here each sub array (B and C) have both left and right indices variables (B is an array with p elements and C is an element with q elements) 
{ 
    int i=0; 
    int j=0; 
    int k=0; 

    while(i < rightp && j < rightq) 
    { 
     if(B[i] <=C[j]) 
     { 
      A[k]=B[i]; 
      i++; 
     } 
     else 
     { 
      A[k]=C[j]; 
      j++; 
      inversions+=(rightp-leftp); //when placing an element from the right array, the number of inversions is the number of elements still in the left sub array. 
     } 
     k++; 
    } 
    if(i=rightp) 
     Copy(A,k,rightp+rightq,C,j,rightq); 
    else 
     Copy(A,k,rightp+rightq,B,i,rightp); 
} 

Я специально запутался в действии вторых аргументов «B» и «C» в вызовах MergeSort. Мне нужно их там так у меня есть доступ к ним для копирования и и слияния, но

---

Я извиняюсь за двусмысленность здесь. Вот результат:

Input (A)= 4 2 53 8 1 19 21 6 
19 
19 
21 
19 
21 
19 
21 
6 
inversions=9 

Очевидно, что это не правильный результат для массива, и по моим подсчетам, инверсии должно равняться 16. Любая помощь или замечания будут весьма благодарны. (Даже критика тоже;)

Answer 1

псевдопользователей-код из Введения в Алгоритмы (Кормена MIT Press.) 2nd Edition:

MERGE -INVERSIONS (A, p, q, r) 
n1 ← q − p + 1 
n2 ← r − q 
create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1] 
for i ← 1 to n1 
    do L[i] ← A[ p + i − 1] 
for j ← 1 to n2 
    do R[ j ] ← A[q + j ] 
L[n 1 + 1] ← ∞ 
R[n 2 + 1] ← ∞ 
i ←1 
j ←1 
inversions ← 0 
counted ← FALSE 
for k ← p to r 
    do 
    if counted = FALSE and R[ j ] < L[i] 
    then inversions ← inversions +n1 − i + 1 
    counted ← TRUE 
    if L[i] ≤ R[ j ] 
    then A[k] ← L[i] 
    i ←i +1 
    else A[k] ← R[ j ] 
    j ← j +1 
    counted ← FALSE 
    return inversions 

Следует отметить, что подсчитанное переменная фактически не требуется. Сортировка слияния по своей природе является рекурсивным алгоритмом. Ваша реализация должна внимательно следить за этим psuedo-кодом. Приспосабливая, когда это необходимо, в соответствии с вашими потребностями. Однако в этом случае. Прямая реализация этого psuedo-кода будет фактически включать инверсии во время классического сортирования слияния.