Hola, quería consultar si con modificar B por 2B en la llamada (r, L) = Merge-and-Count(A, 2B) ya quedaría el algoritmo de este ejercicio, ya que en realidad solo pide que devuelva la cantidad de inversiones, y no necesariamente la lista con los bj originales ordenados. Sino había pensando que podía modificar la condición en el if de merge-and-count, poner 2bj en vez de bj. Nose si voy encaminanda o no, muchas gracias!! El algoritmo completo:
Merge-and-Count(A,B)
Maintain a Current pointer into each list, initialized to point to the front elements
Maintain a variable Count for the number of inversions, initialized to 0
While both lists are nonempty:
Let ai and bj be the elements pointed to by the Current pointer
Append the smaller of these two to the output list
If bj is the smaller element then
Increment Count by the number of elements remaining in A
Endif
Advance the Current pointer in the list from which the smaller element was selected.
EndWhile
Sort-and-Count(L)
If the list has one element then there are no inversions
Else
Divide the list into two halves:
A contains the first n/2 elements
B contains the remaining n/2 elements
(rA, A) = Sort-and-Count(A)
(rB, B) = Sort-and-Count(B)
(r, L) = Merge-and-Count(A, 2B)
Endif
Return r = rA + rB + r, and the sorted list