[C++][Algorytmy] MergeSort i liczenie inwersji

[rochaj]

Kod sortuje i liczy liczbe inwersji, jednak działa zbyt wolno. Jak go zmienić aby działał szybciej?

Kod: Zaznacz cały

#include <cmath>
#include <iostream>
#include <iomanip>
#include <cstdlib>

using namespace std;
 
 int A[1000000],B[1000000];

int MergeSort(int p, int q)
{
    if (p==q)
        return 0;
    int s = (p + q) / 2;
    MergeSort(p, s);
    MergeSort(s+1, q);

    int i = p,l=0;
    int j = s+1;
    for (int k = p; k <= q; k++)
        if (j>q || ( i<=s && A[i] < A[j] ) )
        {
           B[k] = A[i];
           i++;
          
        } else
        {
           B[k] = A[j];
           j++;
          
        }
     for(int k = p ; k <= q; k++)
          A[k] = B[k];
      
}


int main() {
    int n,ile=0;
    ios_base::sync_with_stdio(0);
    cin >>n;
    for (int i=0;i<n;i++) cin>>A[i];
  
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i<j && A[i]>A[j])
            {
                ile++;
            }
        }
    }
 
     MergeSort(0,n-1);      
    for (int i=0;i<n;i++) cout << A[i]<<" ";
    cout<<endl;
    cout<<ile;
    return 0;
}

[Adifek]

Liczysz inwersje w czasie \(\displaystyle{ O(n^2)}\) (co jest dużo wolniejsze od sortowania!), a da się to zrobić w \(\displaystyle{ O(n \ln n)}\), a tutaj w zasadzie przy okazji sortowania