Method merge

CountInversions.java:26–67

(long arr[],long s,long m, long e)

    }
    
    public static long merge(long arr[],long s,long m, long e)
    {
        int n1=(int)(m-s+1);//5
        int n2=(int)(e-m);//5
        long L[]=new long[n1];
        long R[]=new long[n2];
        long count=0;
        // Creating a subarray!
        for(int i=0;i<n1;i++)
        {
            L[i]=arr[(int)(s)+i];
        }
        for(int j=0;j<n2;j++)
        {
            R[j]=arr[(int)(m)+1+j];
        }
        int i=0,j=0,k=(int)(s);
        while(i<n1 && j<n2)
        {
            if(L[i]<=R[j])
            {
                arr[k]=L[i];
                i++;
            }
            else
            {
                arr[k]=R[j];
                count+=n1-i;
                j++;
            }
            k++;
        }
        while(i<n1)
        {
            arr[k++]=L[i++];
        }
        while(j<n2)
        {
            arr[k++]=R[j++];
        }
        return count;
    }
}