Candale Silviu (silviu) Sortarea prin interclasare, sau Mergesort este o metodă eficientă de sortare a elementelor unui tablou, bazată pe următoarea idee: dacă prima jumătate a tabloului are elementele sortate și a doua jumătate are de asemenea elementele sortate, prin interclasare se va obține tabloul sortat.
Sortarea prin interclasare este un exemplu tipic de algoritm divide et impera: se sortează o secvență delimitată de indicii st și dr:
- dacă
st <= dr, problema este elementară, secvența fiind deja sortată - dacă
st < dr:- se împarte problema în subprobleme, identificând mijlocul secvenței,
m = (st + dr) / 2; - se rezolvă subproblemele, sortând secvența delimitată de
stșim, respectiv secvența delimitată dem+1șidr– apeluri recursive; - se combină soluțiile, interclasând cele două secvențe; în acest fel, secvența delimitată de
stșidreste sortată.
- se împarte problema în subprobleme, identificând mijlocul secvenței,
În secvența următoare tabloul tmp se consideră declarat global, de aceeași dimensiune ca v:
void MergeSort(int v[], int st, int dr)
{
if(st < dr)
{
int m = (st + dr) / 2;
MergeSort(v, st , m);
MergeSort(v, m + 1 , dr);
//Interclasare
int i = st, j = m + 1, k = 0;
while( i <= m && j <= dr )
if( v[i] < v[j])
tmp[++k] = v[i++];
else
tmp[++k] = v[j++];
while(i <= m)
tmp[++k] = v[i++];
while(j <= dr)
tmp[++k] = v[j++];
for(i = st , j = 1 ; i <= dr ; i ++ , j ++)
v[i] = tmp[j];
}
}
Observații:
- complexitatea sortării prin interclasare este \( O(n\cdot \log n) \);
- pentru interclasare este este necesar un spațiu de memorie suplimentar, de dimensiunea tabloului care se sortează;
- în secvența de mai sus tabloul
tmpa fost declarat global; declararea sa locală poate duce la depășirea stivei; o soluție pentru această situație poate fi alocarea dinamică a tabloului auxiliar.
