- Queremos contar o número de inversões em um vetor v de tamanho n
 
 - Para simplificar, vamos supor que os elementos do vetor são os números inteiros de 1 até n, em qualquer ordem
 
 - Uma inversão corresponde a um par de índices i, j (não necessariamente adjacente) tal que i < j e v[i] > v[j]
 
 - Exemplo:
    - v = [1 3 5 2 4 6]
	- inversões (3 2), (5 2), (5 4)
 
 - Este problema pode ser usado para comparar duas sequências de preferências sobre itens, e seu resultado nos informa quão semelhantes essas sequências são
    - Isso pode ser útil para aplicações de filtragem colaborativa do tipo sugerir vídeos, músicas ou produtos baseados em suas compras e avaliações passadas
    - No caso desta aplicação queremos comparar duas sequências arbitrárias, enquanto no nosso exemplo simplificado estamos comparando uma sequência com a sequência ordenada
       - Conseguem reduzir (transformar) o problema mais geral no caso simplificado? Quão eficiente é o algoritmo pra fazer essa transformação?
 
 - Conseguimos contar o número de inversões usando um algoritmo simples que utiliza dois laços
   - Qual a eficiência desse algoritmo? n(n-1)/2 = O(n^2)
 
 - Qual o número máximo de inversões num vetor com n elementos? n escolhe 2 = n!/(n-2)!2! = n(n-1)/2
 
 
 
 - Abordagem mais sofisticada usando divisão e conquista
 
    - Ideia é dividir o vetor no meio e conquistar as metades recursivamente
	
	- Vamos classificar as inversões em três tipos:
	   - Esquerda: se i e j <= n/2
	   - Direita: se i e j > n/2
	   - Dividida: se i <= n/2 e j > n/2
	   
	   - As inversões Esquerda e Direita são computadas recursivamente
	   - As divididas tem que ser computadas posteriormente, na fase de combinar as soluções



numInv ContaInv(vetor v, int n) {
	if (n=1) return 0; // caso base
	
	invEsq = ContaInv(1a metade de v, n/2); // Dividir e conquista recursivamente
	invDir = ContaInv(2a metade de v, n/2);
	
	invDiv = ContaInvDivididas(v, n); // Combinar as soluções	
	return invEsq + invDir + invDiv;
}



 - Quão numerosas podem ser as inversões divididas? n^2/4 = O(n^2), considere um vetor com os maiores elementos na primeira metade e os menores na segunda metade.

 - Quão eficientemente conseguimos computar as inversões divididas?
    - E se os subvetores estiverem ordenados?
	   - Exemplo:
	   
	   vl = [1 3 5] vr = [2 4 6] v =[] #inv_div = 0
	   vl = [3 5] vr = [2 4 6] v =[1] #inv_div = 0
	   vl = [3 5] vr = [4 6] v =[1 2] #inv_div = 2
	   vl = [5] vr = [4 6] v =[1 2 3] #inv_div = 2
	   vl = [5] vr = [6] v =[1 2 3 4] #inv_div = 3
	   vl = [] vr = [6] v =[1 2 3 4 5] #inv_div = 3
	   vl = [] vr = [] v =[1 2 3 4 5 6] #inv_div = 3
	   
	   - Ideia central: as inversões divididas que envolvem um elemento y de vr correspondem ao número de elementos restantes (ainda não copiados) em vl no momento em que vr é copiado
	   
	   Demonstração: Seja x um elemento do primeiro subvetor vl e y um elemento do segundo subvetor vr.
	   Se x é copiado antes de y então x <= y. Neste caso não existe inversão envolvendo x e y.
	   Se y é copiado antes de x então y < x. Neste caso o par x, y corresponde a uma inversão dividida.
	   Note que nosso algoritmo só contabiliza inversões divididas nos casos em que elas realmente ocorrem.



(v, numInvDiv) IntercalaEContaInvDivididas(vl, vr) {

	numInvDiv = 0;
	
	i = 1; j = 1; k = 1;
	while (i <= lenght(vl) && j <= lenght(vr)) {
        if (vl[i] <= vr[j])
			v[k++] = vl[i++];
        else { // vl[i] > vr[j]
			v[k++] = vr[j++];
			numInvDiv += length(vl) - i + 1; // número de elementos restantes em vl
		}
	}
    while (i <= length(vl)) v[k++] = vl[i++];
    while (j <= length(vr)) {v[k++] = vr[j++]; numInvDiv += length(vl) - i + 1;}

	return (v, numInvDiv)
}



(v, numInv) OrdenaEContaInv(vetor v, int n) {
	if (n=1) return (v, 0); // caso base
	
	(vl, invEsq) = OrdenaEContaInv(1a metade de v, n/2); // Dividir e conquista recursivamente
	(vr, invDir) = OrdenaEContaInv(2a metade de v, n/2);
	
	(v, invDiv) = IntercalaEContaInvDivididas(vl, vr); // Combinar as soluções	
	return (v, invEsq + invDir + invDiv);
}