# Insertion Sort Advanced Analysis – HackerRank Solution

In this post, we will solve Insertion Sort Advanced Analysis HackerRank Solution. This problem (Insertion Sort Advanced Analysis) is a part of HackerRank Problem Solving series.

## Solution – Insertion Sort Advanced Analysis – HackerRank Solution

### C++

```#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

long long iNum = 0;

void cntInv(vector<int>& a, vector<int>& b, int l, int r){
if(r - l < 2)
return;
int mid = (l + r) / 2;
cntInv(b, a, l, mid);
cntInv(b, a, mid, r);
int i = mid - 1;
int j = r - 1;
int k = r - 1;
while(i >= l && j >= mid){
if(a[j] >= a[i])
b[k--] = a[j--];
else{
iNum += j - mid + 1;
b[k--] = a[i--];
}
}
while(i >= l){
b[k--] = a[i--];
}
while(j >= mid){
b[k--] = a[j--];
}
}

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int T;
cin >> T;
while(T--){
vector<int> a;
int n;
cin >> n;
for(int i = 0; i < n; ++i){
int num;
cin >> num;
a.push_back(num);
}
vector<int> b(a);
iNum = 0;
cntInv(a, b, 0, a.size());

cout << iNum << endl;
}
return 0;
}
```

### Python

```from array import array
from bisect import bisect_right

t = int(input())
for _ in range(t):
n = int(input())
arr = array('I', [int(i) for i in input().split()])
sarr = array('I', [arr[0]])
result = 0
for i in range(1, n):
e = arr[i]
j = bisect_right(sarr, e)
sarr.insert(j, e)
result += i - j
print(result)
```

### Java

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

public class Solution {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);
int t = in.nextInt();

for (int i = 0; i < t; i++) {
int n = in.nextInt();
int[] ar = new int[n];
for (int j = 0; j < n; j++) {
ar[j] = in.nextInt();
//System.err.println(ar[j]);
}
long c = insertSort(ar);
System.out.println(c);
}
}

static long count = 0;

public static void mergesort(int[] arr, int p, int r) {
int q = (p + r) / 2;
if (p < r) {
mergesort(arr, p, q);
mergesort(arr, q + 1, r);
merge(arr, p, q, r);
}
}

public static void merge(int[] arr, int p, int q, int r) {
int[] left = new int[q - p + 1];
int[] right = new int[r - q];
for (int i = 0; i < left.length; i++) {
left[i] = arr[p + i];
}
for (int i = 0; i < right.length; i++) {
right[i] = arr[q + i + 1];
}

int i = 0, j = 0;
for (int k = p; k <= r; k++) {
if (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
count += left.length - i;
j++;
}
} else {
if (i < left.length) {
arr[k] = left[i];
i++;
} else if (j < right.length) {
arr[k] = right[j];
j++;
}
}
}
}

public static long insertSort(int[] ar) {
count = 0;
mergesort(ar, 0, ar.length - 1);
return count;

}
}
```

Note: This problem (Insertion Sort Advanced Analysis) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.