Inversions

This algorithm finds the number of inversions in a given permutation. We are looking for the number of pairs (a,b) where a > b and a is before b. The solution bases on merge sort technique.

Input

n
a(1) a(2) ... a(n)

n – number of elements in a permutation
a(i) – cardinal number between 1 and n

Sample input

6
4 3 1 6 5 2

Output

The number of inversions.

Complexity

In a naive solution we would have to compare each value with all the other on the right, so the complexity would be O(n²). Using merge sort technique we gain complexity O(nlogn).

Source code

#include <stdio.h>
 
using namespace std;
 
int * numbers;
int * tmp;
 
long long merge(int begin, int middle, int end)
{
    int pos = begin;
    int left_it = begin;
    int right_it = middle + 1;
 
    int left_size = middle - begin + 1;
    long long counter = 0;
 
    //tmp copy
    for (int i = begin; i <= end; i++)
        tmp[i] = numbers[i];
 
    //merge
    while (left_it <= middle && right_it <= end)
    {
        if (tmp[left_it] <= tmp[right_it])
        {
            numbers[pos++] = tmp[left_it++];
            left_size--;
        }
        else
        {
            numbers[pos++] = tmp[right_it++];
            counter += left_size;
        }
    }
 
    //insert remaining elements
    while (left_it <= middle)
        numbers[pos++] = tmp[left_it++];
    while (right_it <= end)
        numbers[pos++] = tmp[right_it++];
 
    return counter;
}
 
long long inversion_count(int begin, int end)
{
    if (begin >= end)
        return 0;
 
    int middle = (begin + end) / 2;
    long long l_count = inversion_count(begin, middle);
    long long r_count = inversion_count(middle + 1, end);
 
    return l_count + r_count + merge(begin, middle, end);
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    numbers = new int[n];
    tmp = new int[n];
 
    for (int i = 0; i < n; i++)
        scanf("%d", &numbers[i]);
 
    printf("%lld", inversion_count(0, n-1));
    return 0;
}

#include <stdio.h>

using namespace std;

int * numbers;

int * tmp;

long long merge(int begin, int middle, int end)

{

int pos = begin;

int left_it = begin;

int right_it = middle + 1;

int left_size = middle - begin + 1;

long long counter = 0;

//tmp copy

for (int i = begin; i <= end; i++)

tmp[i] = numbers[i];

//merge

while (left_it <= middle && right_it <= end)

{

if (tmp[left_it] <= tmp[right_it])

{

numbers[pos++] = tmp[left_it++];

left_size--;

}

else

{

numbers[pos++] = tmp[right_it++];

counter += left_size;

}

//insert remaining elements

while (left_it <= middle)

numbers[pos++] = tmp[left_it++];

while (right_it <= end)

numbers[pos++] = tmp[right_it++];

return counter;

}

long long inversion_count(int begin, int end)

{

if (begin >= end)

return 0;

int middle = (begin + end) / 2;

long long l_count = inversion_count(begin, middle);

long long r_count = inversion_count(middle + 1, end);

return l_count + r_count + merge(begin, middle, end);

}

int main()

{

int n;

scanf("%d", &n);

numbers = new int[n];

tmp = new int[n];

for (int i = 0; i < n; i++)

scanf("%d", &numbers[i]);

printf("%lld", inversion_count(0, n-1));

return 0;

}