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,
