Merge sort

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare
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[modificare | modificare sursă]

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ă.