Numărarea inversiunilor cu merge sort
Cât de „amestecată” este o listă? O măsură exactă este numărul de inversiuni: perechi de elemente aflate în ordinea greșită. Forța brută le numără în O(n²); trucul de interviu este să le numeri în timpul interclasării din merge sort, în O(n log n).
Ce este o inversiune
O inversiune este o pereche de poziții i < j cu a[i] > a[j]: un element mai mare apare înaintea unuia mai mic. O listă sortată are 0 inversiuni; una inversată are cele mai multe: n · (n - 1) / 2.
a = [2, 4, 1, 3, 5]
for i in range(len(a)):
for j in range(i + 1, len(a)):
if a[i] > a[j]:
print(f'({a[i]}, {a[j]})') Scrie funcția inversiuni(lista) care returnează numărul de perechi i < j cu lista[i] > lista[j], în O(n log n): o funcție ajutătoare recursivă (ca merge sort) returnează lista sortată și numărul de inversiuni, iar la interclasare adaugi len…
- Scrie sorteaza_si_numara(a) care returnează (lista_sortata, inversiuni).
- La interclasare, când st[i] > dr[j], adaugă len(st) - i.
- inversiuni(lista) returnează a doua valoare. Trebuie să apară: 3, 10, 0, 5, 44850.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan