CODESPTB - Insertion Sort - SPOJ Solution C++ ~ CodingWithArt

➤ Problem Link : CODESPTB

👉 Hint : edit please

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

ll arr[100001];
ll ans=0;
ll tmp[100001];

void Merge(ll l,ll m,ll r)
{
    ll i=l,j=m+1,k=0;
    while(i<=m && j<=r)
    {
        if(arr[i]>arr[j])
        {
            ans+=m-i+1;
            tmp[k++]=arr[j++];
        }
        else
            tmp[k++]=arr[i++];
            
    }
    while(i<=m)
        tmp[k++]=arr[i++];
    while(j<=r)
        tmp[k++]=arr[j++];
    k=0;
    for(i=l;i<=r;i++)
        arr[i]=tmp[k++];
}

void MergeInv(ll l,ll r)
{
	if(l<r)
	{
		ll m=(l+r)/2;
		MergeInv(l,m);
		MergeInv(m+1,r);
		Merge(l,m,r);
	}
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		ll n;
		cin>>n;
		ans=0;
		for(ll i=0;i<n;i++)
			cin>>arr[i];
		MergeInv(0,n-1);
		cout<<ans<<endl;

	}
}

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.

😇Happy Learning!!

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.