Merge sort

Exemplu al rulării mergesort pe o listă de numere aleatoare

În informatică, merge sort (sau mergesort, denumit și algoritm de sortare prin interclasare) este un algoritm de sortare cu complexitatea $O(n \log{n})$, inventat de John von Neumann în 1945. Este un exemplu de algoritm de tip divide et impera.

Algoritmul

Algoritmul merge sort execută următorii pași

1. Dacă lista este de lungime 0 sau 1, atunci este deja sortată. Altfel:
2. Împarte lista nesortată în două subliste aproximativ egale.
3. Sortează fiecare sublistă recursiv prin reaplicarea algoritmului merge sort.
4. Se interclasează cele două liste și se obține lista inițială sortată.