Buenas! quería saber si este algoritmo es correcto, probé correrlo en unos ejemplos y funciona bien pero para confirmar. Aprovecho también para consultar, en la parte c, como son dos llamadas recursivas en conjuntos de tamaño ~ n/2 y como el merge es O(n), se puede justificar que es O(n log n) utilizando como resultado teórico la recurrencia 5.1, o haría falta demostrarlo mediante los métodos del libro? Desde ya muchas gracias!
Algoritmo Inversiones-Significativas(L):
n = longitud(L)
si n <= 1:
devolver 0, L // Devolvemos 0 inversiones y la lista original
Dividir L en dos mitades: L_izq y L_der
contar_izq, L_izq = Inversiones-Significativas(L_izq)
contar_der, L_der = Inversiones-Significativas(L_der)
contar_dividida, lista_mezclada = Mezclar-y-Contar-Significativas(L_izq, L_der)
devolver contar_izq + contar_der + contar_dividida, lista_mezclada
Función Mezclar-y-Contar-Significativas(L_izq, L_der):
i = 1, j = 1, contar = 0
lista_mezclada = []
mientras i <= longitud(L_izq) y j <= longitud(L_der):
si L_izq[i] <= 2 * L_der[j]:
Añadir L_izq[i] a lista_mezclada
i = i + 1
sino:
Añadir L_der[j] a lista_mezclada
contar = contar + (longitud(L_izq) - i + 1) // Contamos inversiones significativas
j = j + 1
end mientras
Añadir los elementos restantes de L_izq a lista_mezclada
Añadir los elementos restantes de L_der a lista_mezclada
devolver contar, lista_mezclada