Count inversion

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.5 kB
3
Indexable
Never
#include <iostream>
using namespace std;

int merge(int *arr, int s, int e)
{
    int mid= (s+e)/2;
    int length1= mid-s+1;
    int length2= e-mid;
    int count = 0;
    
    int *first= new int[length1];
    int *second= new int[length2];
    
    int mainArrayIndex=s;
    for(int i=0; i<length1; i++)
    {
        first[i]= arr[mainArrayIndex++];
    }
    
    mainArrayIndex= mid+1;
    for(int j=0; j<length2; j++)
    {
        second[j]= arr[mainArrayIndex++];
    }
    
    int index1=0;
    int index2=0;
    mainArrayIndex=s;
    
    
    while(index1<length1 && index2<length2)
    {
        if(first[index1]<=second[index2])
        {
            arr[mainArrayIndex++]=first[index1++];
        }
        else
        {
            arr[mainArrayIndex++]=second[index2++];
            count += length1 - index1;
        }
    }
    
    while(index1<length1)
    {
        arr[mainArrayIndex++]=first[index1++];
    }
    
    while(index2<length2)
    {
        arr[mainArrayIndex++]=second[index2++];
    }
    
    delete []first;
    delete []second;
    
    return count;
}

int mergeSort(int *arr, int s, int e)
{
    int count = 0;
    if(s<e) {
    int mid= (s+e)/2;
    count += mergeSort(arr, s, mid);
    count += mergeSort(arr, mid+1, e);
    count += merge(arr, s, e);
    }
    return count;
}

int main()
{
    int arr[4]= {6,5,4,3};
    int n=4;
    int count = mergeSort(arr, 0, n-1);
    
    cout<<count;

    return 0;
}