Count Inversion using merge sort

Question

i wrote the code of count inversion using merge sort in C++ but i am getting wrong answer

#include <bits/stdc++.h>

using namespace std;

long long merge(long long *arr,long long s, long long mid,long long e){
    long long count =0;
    long long temp[e-s+1];
    long long i = s;
    long long j = mid+1;
    long long k =0;
    while(i<=mid && j<=e){
        if(arr[i]<arr[j]){
            temp[k++] = arr[i++];
        }else{
            temp[k++] = arr[j++];

            count = count + (mid+1)-i;
        }
    }
    while(i<=mid){
        temp[k++] = arr[i++];
    }
    while(j<=e){
        temp[k++] = arr[j++];
    }
    k=0;
    for(i=s;i<=e;i++){
        arr[i] = temp[k++];
    }
    return count;
}

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

int main(){
    long long x;
    cin >> x;
    long long arr[x];
    for(long long i=0;i<x;i++){
        cin >> arr[i];
    }
    long long N =x;
    cout << mergeSort(arr,0,N-1);
}

it fails this test case

Array size : 42
elements : 468 335 1 170 225 479 359 463 465 206 146 282 328 462 492 496 443 328 437 392 105 403 154 293 383 422 217 219 396 448 227 272 39 370 413 168 300 36 395 204 312 323

Correct Output

output of my code

Instead of `long long` why not [`int64_t`](https://en.cppreference.com/w/cpp/types/integer)? — tadman, Mar 16 '21 at 09:47
Looks like an off-by-one error and this is where a debugger is invaluable. Have you stepped through the code? You might be processing/counting the same element twice. — tadman, Mar 16 '21 at 09:48
Note: `long long arr[x];` where `x` is a variable is non-standard C++. `std::vector arr(x)` is the standard alternative. — tadman, Mar 16 '21 at 09:48
I can't compile your program. Please read [Why should I **not** `#include `?](https://stackoverflow.com/Questions/31816095/Why-Should-I-Not-Include-Bits-Stdc-H.) — Ted Lyngmo, Mar 16 '21 at 09:50
At least here: `while(i<=mid) { temp[k++] = arr[i++];}`: you forgot to increment `count` — Damien, Mar 16 '21 at 09:54
`count = count + (mid+1)-i;` is suspicious. If the body of that while is "an inversion" why are you changing count by anything other than 1? — Caleth, Mar 16 '21 at 10:22

Count Inversion using merge sort

0 Answers0