El tercer problema de la sesión, UVa 10810. Contar las parejas una por una cuesta demasiado, y la salida es partir el arreglo por la mitad: las parejas de cada mitad son el mismo problema más chico, y las que cruzan se cuentan gratis mientras se mezcla. Aquí corre el código del ejercicio, con las dos posiciones de la mezcla marcadas.
¿Cuántas parejas fuera de orden tiene? Cuéntelas a mano antes de ejecutar.
En azul la posición i, que recorre la mitad izquierda, y en naranja la j, que recorre la derecha.
Sin solución aquí. La suma que cuenta las parejas que cruzan es medio − i, y solo aparece cuando sale un elemento de la derecha. Explique por qué nunca hay que sumar nada cuando sale uno de la izquierda. Después pruebe con el arreglo al revés del todo y compruebe que el total es n(n−1)/2, y diga en qué nivel de la recursión se cuenta la mayor parte.