// Podstawy Informatyki
// Zliczanie ilosci inwersji w podanej serii liczb.

#include <stdio.h>

// polaczIZliczaj 2 posortowane podtablice tab[lewa ... srodek] i tab[srodek + 1 ... prawa]
int polaczIZliczaj(int tab[], int tmp[], int lewa, int srodek, int prawa)
{
	int k = lewa, i = lewa, j = srodek + 1;
	int licznik_inwersji = 0;

	// Wykonuj dopoki istnieja elementy w tablicy.
	while (i <= srodek && j <= prawa)
	{
		if (tab[i] <= tab[j]) {
			tmp[k++] = tab[i++];
		}
		else {
			tmp[k++] = tab[j++];
			licznik_inwersji += (srodek - i + 1);
		}
	}

	// Kopiowanie.
	while (i <= srodek)
		tmp[k++] = tab[i++];


	for (int i = lewa; i <= prawa; i++)
		tab[i] = tmp[i];

	return licznik_inwersji;
}

// Posortuj tablice tab [lewa..prawa] wykorzystujac pomocnicza tablice tmp.
int sortujIZliczaj(int tab[], int tmp[], int lewa, int prawa)
{
	// Przypadek podstawowy - maly problem.
	if (prawa == lewa)
		return 0;

	// Znajdz miejsce (indeks) podzialu tablicy.
	int srodek = (lewa + ((prawa - lewa) >> 1));
	int licznik_inwersji = 0;

	// Dzielimy dopoki nie osiagniemy przypadku podstawowego,
	// a nastepnie scalamy.

	licznik_inwersji += sortujIZliczaj(tab, tmp, lewa, srodek);		// podziel na lewo
	licznik_inwersji += sortujIZliczaj(tab, tmp, srodek + 1, prawa); // podziel na prawo
	licznik_inwersji += polaczIZliczaj(tab, tmp, lewa, srodek, prawa);	// polacz polowy

	return licznik_inwersji;
}

int main()
{
	int tab[] = { 6, 2, 4, 1, 5, 3, 7, 8 };

	int n = sizeof(tab)/sizeof(tab[0]);

	int tmp[n];
	for (int i = 0; i < n; i++)
		tmp[i] = tab[i];

	printf("Liczba inwersji: %d.", sortujIZliczaj(tab, tmp, 0, n - 1));

	return 0;
}