Merge sort: împarte și stăpânește
Sortările de până acum erau O(n²). Merge sort coboară la O(n log n) cu o idee simplă și foarte puternică: împarte lista în două, sortează fiecare jumătate recursiv, apoi interclasează cele două jumătăți sortate. Strategia se numește „împarte și stăpânește” (divide and conquer).
Pasul cheie: interclasarea
Ai două liste deja sortate. Cum obții o singură listă sortată? Cu doi indici, unul pentru fiecare listă (exact tehnica two pointers): compari elementele curente, îl iei pe cel mai mic și avansezi în lista lui. Când o listă se termină, adaugi restul celeilalte.
def interclaseaza(a, b):
rezultat = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
rezultat.append(a[i]) Scrie funcțiile interclaseaza(a, b) (două liste sortate → o listă sortată, cu doi indici) și merge_sort(lista) (recursiv: împarte, sortează jumătățile, interclasează). merge_sort returnează o listă nouă. Nu folosi sort() sau sorted().
- Scrie interclaseaza cu doi indici și adaugă la final resturile ambelor liste.
- În merge_sort: caz de bază len(lista) <= 1, apoi împarte la mij = len(lista) // 2.
- Trebuie să apară: [3, 9, 10, 27, 38, 43, 82], [], [1, 5, 5], [1, 2].
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan