1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
// C program to Count 
// Inversions in an array 
// using Merge Sort 
#include <bits/stdc++.h>
#include <cstdio>
#include <vector>
#include "teatr.h"
#include "message.h"
#include <cmath> 

unsigned long long int _mergeSort(int arr[], int temp[], int left, int right); 
unsigned long long int merge(int arr[], int temp[], int left, int mid, int right); 

/* This function sorts the input array and returns the 
number of inversions in the array */
unsigned long long int mergeSort(int arr[], int array_size) 
{ 
	int* temp = (int*)malloc(sizeof(int) * array_size); 
	return _mergeSort(arr, temp, 0, array_size - 1); 
} 

/* An auxiliary recursive function that sorts the input array and 
returns the number of inversions in the array. */
unsigned long long int _mergeSort(int arr[], int temp[], int left, int right) 
{ 
	int mid;
	unsigned long long int inv_count = 0; 
	if (right > left) { 
		/* Divide the array into two parts and call _mergeSortAndCountInv() 
	for each of the parts */
		mid = (right + left) / 2; 

		/* Inversion count will be sum of inversions in left-part, right-part 
	and number of inversions in merging */
		inv_count = _mergeSort(arr, temp, left, mid); 
		inv_count += _mergeSort(arr, temp, mid + 1, right); 

		/*Merge the two parts*/
		inv_count += merge(arr, temp, left, mid + 1, right); 
	} 
	return inv_count; 
} 

/* This funt merges two sorted arrays and returns inversion count in 
the arrays.*/
unsigned long long int merge(int arr[], int temp[], int left, int mid, int right) 
{ 
	int i, j, k; 
	unsigned long long int inv_count = 0; 

	i = left; /* i is index for left subarray*/
	j = mid; /* j is index for right subarray*/
	k = left; /* k is index for resultant merged subarray*/
	while ((i <= mid - 1) && (j <= right)) { 
		if (arr[i] <= arr[j]) { 
			temp[k++] = arr[i++]; 
		} 
		else { 
			temp[k++] = arr[j++]; 

			/*this is tricky -- see above explanation/diagram for merge()*/
			inv_count = inv_count + (mid - i); 
		} 
	} 

	/* Copy the remaining elements of left subarray 
(if there are any) to temp*/
	while (i <= mid - 1) 
		temp[k++] = arr[i++]; 

	/* Copy the remaining elements of right subarray 
(if there are any) to temp*/
	while (j <= right) 
		temp[k++] = arr[j++]; 

	/*Copy back the merged elements to original array*/
	for (i = left; i <= right; i++) 
		arr[i] = temp[i]; 

	return inv_count; 
} 

int widownia[1000000];

/* Driver program to test above functions */
int main(int argv, char** args) 
{ 
	int n;

	if(MyNodeId()==0)
	{
		n=GetN();
		for(int i=0;i<n;i++)
		{
			widownia[i]=GetElement(i);
		}
		printf("%llu\n", mergeSort(widownia, n)); 
		return 0; 
	}

	return 0;
}