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

Question

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

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

Это работало отлично для небольших размеров массива, но как-то, когда я масштабированием массив Шифрование до 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; 
}