COUNT-INVERSIONS-MERGESORT hackerrank Solution - Correct, Optimal and Working

#include <cstdio>
#include <iostream>

using namespace std;

int arr[100001];
int temp[100001];

long long int merge(int start, int mid, int end) {
    long long int count = 0;
    int i = start, j = mid, index = start;
    while (i <= (mid - 1) && j <= end) {
        if (arr[i] <= arr[j]) {
            temp[index++] = arr[i++];
        } else {
            temp[index++] = arr[j++];
            count += (mid - i);
        }
    }

    while (i <= mid - 1) {
        temp[index++] = arr[i++];
    }

    while (j <= end) {
        temp[index++] = arr[j++];
    }

    for (int i = start; i <= end ; i++) {
        arr[i] = temp[i];
    }

    return count;
}

long long int sort(int start, int end) {
    if (start >= end) {
        return 0;
    }

    long long int count = 0;
    int mid = start + (end-start)/2;
    count += sort(start, mid);
    count += sort(mid + 1, end);
    count += merge(start, mid + 1, end);
    return count;
}

long long int count_inv(int n) {
    return sort(0, n - 1);
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n ; i++) {
            scanf("%d", &arr[i]);
        }
        printf("%lld\n", count_inv(n));
    }
    return 0;
}

470+ Solutions to various Programming Questions

Subscribe to my weekley newsletter