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 ) {\displaystyle O(n\log {n})} , inventat de John von Neumann în 1945. Este un exemplu de algoritm de tip divide et impera.

Descriere

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ă.
 Acest articol din domeniul informaticii este deocamdată un ciot. Puteți ajuta Wikipedia prin dezvoltarea lui.