solution to https://www.hackerrank.com/contests/kod-o-sis/challenges/insertion-sort/

Insertion_sort_ANalysis

#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
using namespace std ;
long long mergeSort(vector<int> &v) {
    if (v.size() <= 1) {
        return 0;
    }

    long long ans = 0;
    int m = v.size() / 2;
    vector<int> v1(m);
    copy(v.begin(), v.begin() + m, v1.begin());
    vector<int> v2(v.size() - m);
    copy(v.begin() + m, v.end(), v2.begin());

    ans += mergeSort(v1);
    ans += mergeSort(v2);

   std::vector<int>:: iterator it = v.begin();
   std::vector<int>:: iterator it1 = v1.begin();
    std::vector<int>::iterator it2 = v2.begin();
    while (it1 != v1.end() && it2 != v2.end()) {
        if (*it1 <= *it2) {
            *it++ = *it1++;
        } else {
            ans += v1.end() - it1;
            *it++ = *it2++;
        }
    }
    while (it1 != v1.end()) {
        *it++ = *it1++;
    }
    while (it2 != v2.end()) {
        *it++ = *it2++;
    }

    return ans;
}
int main()
{

    int t,i ;
    int p ;
    scanf("%d",&t);
    while(t--)
    {
        int n ;
        scanf("%d",&n);
        vector <int> v ;
        for (i=0 ; i< n ; i++)
        {

            scanf("%d",&p);
            v.push_back(p);
        }
        cout<<mergeSort(v)<<"\n";
    }
    return 0 ;
}