数组中的反转计数数。使用合并排序

对于那些不知道反转的人。

反演

给定一个由N个整数组成的数组A，该数组的求反定义为任意一对索引（i，j），使得i <j并且A [i]> A [j]。

简而言之：

{inv}（A）= {（A（i），A（j）），i <j {和} A（i）> A（j）}

例如，对于条目对（2,1），数组a = {2,3,1,5,4}具有三个反转：（1,3），（2,3），（4,5） ，（3,1），（5,4）。

总反转计数= 3。

好吧，我试图通过利用标准合并排序来解决这个问题。我认为这是这样的。

假设在某个阶段，合并排序的partA和partb是

部分A- [1,2,3]。

B部分-[4,5]

现在，让X为第一个数组partA的元素。Y是第二个数组，partB。

如果将X复制到输出数组（即，如果X <Y）-那么我们就没有反转。

否则，如果将Y复制到输出数组（即，如果X> Y）。然后我们得到Inversion count = count + mid-i + 1。（i是该元素的位置）。当按升序排序时，位置j> i，X [j]> Y的所有元素。

这是代码的更多详细信息。

#include <iostream>
#include <vector>
using namespace std;

vector<int> a;
vector<int> c;
void merge(int low, int high, int mid);
void mergesort(int low, int high)
{
 int mid;
 if (low < high)
 {
     mid=(low+high)/2;
     mergesort(low,mid);
     mergesort(mid+1,high);
     merge(low,high,mid);
 }
return ;
}

int count ; //to store the inversion count
void merge(int low, int high, int mid)
{
int i, j, k;
i = low;
k = low;
j = mid + 1;
// standard merging from merge sort
while (i <= mid && j <= high)
{
    if (a[i] < a[j])
    {
        c[k] = a[i];
        k++;
        i++;
    }
    else
    {
        c[k] = a[j];
        k++;
         j++;
      //   cout<<a[i]<<" "<<mid<<" "<<i<<"\n";
         count += mid - i+1; // This is where the trick occurs, if X > Y,
         //eg. in [3, 4, 5] and [1,2]
         //if(3>1) then 4,5 is obviously greater then 1, thus making count as mid - i+1              
     }
 }
while (i <= mid)
{
    c[k] = a[i];
    k++;
    i++;
}
while (j <= high)
{
    c[k] = a[j];
    k++;
    j++;
}
for (i = low; i < k; i++)
{
    a[i] = c[i];
 }
}
int main()
{
//int a[20], i, b[20];
int T;
cin>>T;
while(T--){
    //cout<<"enter  the elements\n";
    int N;
    cin>>N;
    count =0;
    a.clear(); a.resize(N);
    c.clear(); c.resize(N);
    for (int i = 0; i < N; i++)
    {
        cin>>a[i];
    }
    mergesort(0, N-1);

    cout<<count<<"\n";
}
}

好的，现在让我感到怀疑的是，我相信上述实现的逻辑足以解决反转的数量，但是由于某些奇怪的原因，我不知道是什么导致了WA。

我在这个问题上停留了一段时间，无法弄清楚。这不是一个家庭作业问题，只是我认为逻辑没有错，并且代码仍然无法正常工作，可能是什么原因？帮助！。

Ideone链接- https://ideone.com/nmvl7i

关于Spoj的问题-http: //www.spoj.com/problems/INVCNT/

注意：前两个测试用例工作正常，提交时我得到了WA。