Merge sort

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

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

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ă.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.