Lucrare de laborator nr. 3 la Structuri de Date si Algoritmi "Metoda de sorare: MERGE SORT" - Tutunaru Sergiu

Extras din document

Tema: Metoda de sortare : MERGE SORT Sarcina: De studiat metoda de sortare si de labrat un program C cu agoritmul ei. Î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ă.