Metode de sortare

Merge Sort [interclasare]


Cazul mediu : O(N log N)

Cazul defavorabil : O(N log N)

Memorie folosita : O(N)

Stabil : DA

Descriere :

În cazul sortării prin interclasare vectorii care se interclasează sunt două secvențe ordonate din același vector. Sortarea prin interclasare utilizează metodă Divide et Impera: -se împarte vectorul în secvențe din ce în ce mai mici., astfel încât fiecare secvența să fie ordonată la un moment dat și interclasată cu o altă secvența din vector corespunzătoare. -practic interclasarea va începe când se ajunge la o secvența formată din două elemente. Această odată ordonată se va interclasa cu o altă corespunzătoare. Cele două secvențe vor alcătui în subșir ordonat din vector mai mare care la rândul lui se va interclasa cu subșirul corespunzător s.a.m.d.