# HackerRank Merge Sort: Counting Inversions problem solution

In this HackerRank Merge Sort: Counting Inversion Interview preparation kit problem In an array, arr, the elements at indices i and j (where i < j) form an inversion if arr[i] > arr[j]. In other words, inverted elements arr[i] and arr[j] are considered to be "out of order".

## Problem solution in Python programming.

```def merge(a, l, m, h):
c = []
i = l
j = m + 1
s = 0

while i <= m and j <= h:
if a[i] > a[j]:
# there is an inversion
s += (m - i + 1)
c.append(a[j])
j += 1
else:
c.append(a[i])
i += 1

while i <= m:
c.append(a[i])
i += 1
while j <= h:
c.append(a[j])
j += 1

a[l: h + 1] = c

return s

def count(a, l, h):
if l >= h:
return 0
#print(l, h)
m = l + (h - l) // 2
s = 0
s += count(a, l, m)
s += count(a, m + 1, h)

s += merge(a, l, m, h)
return s

def count_inversions(a):
return count(a, 0, len(a) - 1)

t = int(input().strip())
for a0 in range(t):
n = int(input().strip())
arr = list(map(int, input().strip().split(' ')))
print(count_inversions(arr))```

## Problem solution in Java Programming.

```import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

private static long mergeSortCount(int[] a, int[] aux, int from, int to) {
if (from >= to) { return 0; }
int mid = (from + to) >>> 1;
long count = 0L;
count += mergeSortCount(a, aux, from, mid);
count += mergeSortCount(a, aux, mid + 1, to);
count += merge(a, aux, from, mid, to);
return count;
}

private static long merge(int[] a, int[] aux, int from, int mid, int to) {
System.arraycopy(a, from, aux, from, to - from + 1);
long count = 0L;
int i = from, j = mid + 1;
for (int k = from; k <= to; k++) {
if (i > mid) {
a[k] = aux[j++];
} else if (j > to) {
a[k] = aux[i++];
} else if (aux[j] < aux[i]) {
a[k] = aux[j++];
count += mid - i + 1;
} else {
a[k] = aux[i++];
}
}
return count;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for(int a0 = 0; a0 < t; a0++){
int n = in.nextInt();
int arr[] = new int[n];
for(int arr_i=0; arr_i < n; arr_i++){
arr[arr_i] = in.nextInt();
}
System.out.println(mergeSortCount(arr, new int[n], 0, n - 1));
}
}
}```

### Problem solution in C++ programming.

```#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

uint64_t insertionSort(vector<int> &ar, int low, int high) {
if (high - low < 2) {
return 0;
}

int mid = (low + high) / 2;
uint64_t count;

count = insertionSort(ar, low, mid);
count += insertionSort(ar, mid, high);

vector<int> aux(ar.begin() + low, ar.begin() + mid);
int walk = mid;
int cur = low;
int i = 0;
while ((i < aux.size()) && (walk < high)) {
if (ar[walk] < aux[i]) {
ar[cur++] = ar[walk++];
count += (walk - cur);
} else {
ar[cur++] = aux[i++];
}
}

while(i < aux.size()) {
ar[cur++] = aux[i++];
}

#if 0
for (int i = low + 1; i < high; i++) {
int cur = ar[i];
int j;
for (j = i - 1; (j >= low) && (cur < ar[j]); j--) {
ar[j + 1] = ar[j];
count++;
}

ar[j+1] = cur;
}
#endif

return count;
}

int mergeSort(vector<int> & a) {
int count = 0;

if (a.size() >= 2) {
vector<int> first(a.begin(), a.begin() + a.size() / 2);
vector<int> second(a.begin() + a.size() / 2, a.end());

count += mergeSort(first);
count += mergeSort(second);
//cout << first.size() << ":" << second.size() << ":" << count << endl;

int i = 0, j = 0;
while (i < first.size() && j < second.size()) {
if (first[i] <= second[j]) {
a[i + j] = first[i];
i++;
} else {
a[i + j] = second[j];
count += (first.size() - i);
//cout << count << "-" << (first.size() - i) << endl;
j++;
}
}

while (i < first.size()) {
a[i + j] = first[i];
i++;
}

while (j < second.size()) {
a[i + j] = second[j];
j++;
}
}

return count;
}

uint64_t count_inversions(vector<int> &a) {
#if 0
int count = 0;

for (int i = 1; i < a.size(); i++) {
if (a[i] < a[i-1]) {
int idx = i;
while ((idx != 0)  && (a[idx] < a[idx - 1])) {
swap(a[idx], a[idx - 1]);
idx--;
count++;
}
}
}
#endif
return insertionSort(a, 0, a.size());
}

int main(){
int t;
cin >> t;
for(int a0 = 0; a0 < t; a0++){
int n;
cin >> n;
vector<int> arr(n);
for(int arr_i = 0;arr_i < n;arr_i++){
cin >> arr[arr_i];
}
cout << count_inversions(arr) << endl;
}
return 0;
}```

### Problem solution in C programming.

```#include <stdio.h>
#include <stdint.h>
#include <string.h>

#define RUN_TEST_CASES(VAR) int VAR##_total; scanf("%d", & VAR##_total); \
for(int VAR=1; VAR<=VAR##_total; ++VAR)

typedef unsigned long long ull;

ull merge(int *a, const int first, const int last)
{
if (last - first == 1)
return 0;

if (last - first == 2)
{
if (a[first + 1] < a[first])
{
int tmp = a[first];
a[first] = a[first + 1];
a[first + 1] = tmp;

return 1;
}

return 0;
}

int m = first + (last - first) / 2;

ull inversions = merge(a, first, m);
inversions += merge(a, m, last);

int lo = first, hi = m;
int t = first;

static int temp[100001];

while (lo < m && hi < last)
{
if (a[lo] <= a[hi])
{
temp[t++] = a[lo++];
continue;
}

temp[t++] = a[hi++];
inversions += m - lo;
}

while (lo < m) temp[t++] = a[lo++];
while (hi < last) temp[t++] = a[hi++];

for (int j = first; j < last; ++j)
a[j] = temp[j];

return inversions;
}

int main()
{
#ifdef _DEBUG
char FNAME[250];
strcpy(FNAME, __FILE__);
strcpy(strchr(FNAME, '.'), ".txt");
freopen(FNAME, "rt", stdin);
#endif

RUN_TEST_CASES(test_case)
{
int a[100001];

int n;
scanf("%d", &n);
for (int j = 0; j < n; ++j)
scanf("%d", &a[j]);

printf("%llu\n", merge(a, 0, n));
}
}```

### Problem solution in JavaScript programming.

```'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});

process.stdin.on('end', function() {
inputString = inputString.replace(/\s*\$/, '')
.split('\n')
.map(str => str.replace(/\s*\$/, ''));

main();
});

return inputString[currentLine++];
}

function countInversions(arr) {
return sortAndCount(arr);
}

function sortAndCount(arr) {
if (arr.length < 2) {
return 0;
}

var mid = Math.floor(arr.length / 2);
var left = arr.slice(0, mid);
var right = arr.slice(mid);

return sortAndCount(left) + sortAndCount(right) + mergeSortAndCount(arr, left, right);
}

function mergeSortAndCount(arr, left, right) {
var i = 0, leftIndex = 0, rightIndex = 0, inversions = 0;

while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] <= right[rightIndex]) {
arr[i] = left[leftIndex];
leftIndex++;
} else {
arr[i] = right[rightIndex];
rightIndex++;
inversions += (left.length - leftIndex);
}

i++;
}

while (leftIndex < left.length) {
arr[i] = left[leftIndex];
leftIndex++;
i++;
}

while (rightIndex < right.length) {
arr[i] = right[rightIndex];
rightIndex++;
i++;
}

return inversions;
}

function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

for (let tItr = 0; tItr < t; tItr++) {

const arr = readLine().split(' ').map(arrTemp => parseInt(arrTemp, 10));

const result = countInversions(arr);

ws.write(result + '\n');
}

ws.end();
}```