code. compile. run. debug. share.
Source Code
Language
/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <iostream>
// #include <bits/stdc++.h>
using namespace std;
long _merge(long arr[], long temp[], long _left, long mid, long _right)
{
// int i,j,k;
long inv_Count = 0;
long i = _left; // for left subarray
long j = mid; // for right subarray
long k = _left; // for resultant merged array
while ((i <= mid - 1) && (j <= _right))
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
// inv_Count += (mid-i);
temp[k++] = arr[j++];
inv_Count += (mid - i);
}
}
while (i <= mid - 1)
{
temp[k++] = arr[i++];
}
while (j <= _right)
{
temp[k++] = arr[j++];
}
for (long i = _left; i <= _right; i++)
{
arr[i] = temp[i];
}
return inv_Count;
}
long _mergeSort(long arr[], long temp[], long _left, long _right)
{
long mid, inv_Count = 0;
if (_right > _left)
{
mid = (_left + _right) / 2;
inv_Count += _mergeSort(arr, temp, _left, mid);
inv_Count += _mergeSort(arr, temp, mid + 1, _right);
inv_Count += _merge(arr, temp, _left, mid + 1, _right);
}
return inv_Count;
}
int main()
{
long t;
cin >> t;
while (t--)
{
// cout << t << endl;
long n;
cin >> n;
long arr[n];
for (long i = 0; i < n; i++)
{
cin >> arr[i];
}
long temp[n];
long ans = _mergeSort(arr, temp, 0, n - 1);
cout << ans << endl;
}
return 0;
}
Compiling Program...
Standard Input:
Interactive Console
Text
Program is not being debugged. Click "Debug" button to start program in debug mode.
| # | Function | File:Line |
|---|
| Variable | Value |
|---|
| Register | Value |
|---|
| Expression | Value |
|---|
| # | Description |
|---|