Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.5 kB
0
Indexable
Never
public:
    // arr[]: Input Array
    // N : Size of the Array arr[]
    // Function to count inversions in the array.
    
    long long int merge(long long arr[], long long left, long long mid, long long right){
        long long int countInv = 0;
        long long temp[right+1];
        long long i, j, k;
        
        i = left;
        j = mid;
        k = left;
        
        while(i <= mid-1 && j <= right){
            if(arr[i] <= arr[j]){
                temp[k++] = arr[i++];
            }
            else {
                temp[k++] = arr[j++];
                
                countInv += mid-i;
            }
        } 
        
        while(i<= mid-1)
            temp[k++] = arr[i++];
            
        while(j <= right){
            temp[k++] = arr[j++];
        }
        
        for(i=left; i<=right; i++){
            arr[i] = temp[i];
        }
        
        return countInv;
    }
    
    
    long long int mergeSort(long long arr[], long long left, long long right){
        
        long long int countInv = 0;
        long long mid = left + (right-left)/2;
        if(left < right){
            countInv += mergeSort(arr, left, mid);
            countInv += mergeSort(arr, mid+1, right);
            
            countInv += merge(arr, left, mid+1, right);
        }
        
        return countInv;
    }
    
    long long int inversionCount(long long arr[], long long n){
        
        return mergeSort(arr, 0, n-1);
    }