Сортировка слиянием и алгоритм инверсии

Question

Хорошо, мой вопрос, чтобы найти количество инверсий в данном массиве.

Прочитав алгоритм инверсии, я понял, что мне просто нужно добавить 1 строку кода в алгоритм слияния, который я написал несколько дней назад.

Это отлично работает для небольших размеров массива, но почему-то, когда я масштабирую массив до 100000 целых чисел, ответ неверен

Вот функция слияния, к которой я добавил эту одну строку.

int merge(int arr[],int low,int mid,int high)
{
    int i,j,k;
    int arr1[11];
    int arr2[11];
    for(i=0;i<mid-low+1;i++)
        arr1[i]=arr[low+i];
    for(j=0;j<high-mid;j++)
        arr2[j]=arr[mid+1+j];
    arr1[i]=9999999;
    arr2[j]=9999999;    
    i=0;
    j=0;
    for(k=low;k<=high;k++)
    {
        if(arr1[i]<=arr2[j])
        {
            arr[k]=arr1[i];
            i++;
        }   
        else
        {
            {
                arr[k]=arr2[j];
                j++;
                count=count+mid-low+1-i; //Inversion counter. 
            }
        }       
    }
    return(0);  
}   

Может кто-нибудь сказать мне, что не так с этим?

Я часами пытался это выяснить, но мне не повезло. Любой вклад будет оценен. Спасибо!

Answer 1

long long int count[200200];

int merge()
{
       long long int a[200200],n,left,right,e,i;
       scanf("%lld",&n);
       for( i = 0 ; i< n ; i++)
       {
               scanf("%lld",&a[i]);
               count[i] = 0;
           }
    long long int size,l1,h1,l2,h2,j,k,temp[200200];
    for(size = 1 ; size < n ; size = size *2)
    {
        l1 = 0;
        k = 0;
        while(l1 + size < n)
        {
            h1 = l1 + size - 1;
            l2 = h1 + 1;
            h2 = l2 + size - 1;
            if(h2 >=n )
            h2 = n - 1;
            i =l1;
            j =l2;
            left = count[h1];
            right= count[h2];
            e = 0; 
            while( i <= h1 && j <= h2)
            {
                if(a[i] <= a[j])
                {
                    temp[k++] = a[i++];
                }
                else
                {
                    e = e + h1 - i + 1;
                    temp[k++] = a[j++];
                }
            }
            count[h2] = left + right + e;
            while(i<=h1)
                temp[k++]=a[i++];
            while(j<=h2)
                temp[k++]=a[j++];
            for( i = l1 ; i <= h2 ;i++)
        //    printf("%d ",temp[i]);
        //    printf("\n");
            l1 = h2 + 1;
        }
        for(i = l1 ; k < n ; i++)
        {
            temp[k++] = a[i];
        }
        for( i = 0 ; i < n ; i++)
        {
        //    printf(" %d = %d ",i,count[i]);
            a[i] = temp[i];
        }
    }
    printf("%lld\n\n",count[n-1]);
    return 0;
}



int main()
{

      merge(); 
      return 0;
}