Marele Intelept a venit sa va explice algoritmul MergeSort. Algoritmul MergeSort este folosit pentru a sorta siruri. Acesta functioneaza in felul urmator: Fie functia recursiva $MergeSort(i,j)$ care sorteaza sirul pe intervalul $(i,j)$. La inceput se apeleaza functia $MergeSort(1,n)$ pentru a sorta tot vectorul. Functia $MergeSort(i,j)$ functioneaza in felul urmator: se determina mijlocul intervalulul $mij = (i + j) / 2$ si se apeleaza pe rand functiile $MergeSort(i,mij)$ si $MergeSort(mij + 1, j)$, dupa care cele $2$ siruri tocmai sortate se interclaseaza obtinandu-se sirul sortat intre pozitiile $i$ si $j$.

* ==user(user="wefgef" type="tiny")==: Ar merge pus un pseudocod aici pentru mergesort.

==code(cpp) |
int SOL = 0;
void mergesort(int left, int right) {
    ++SOL;
 
    bool sorted = true;
    for (int i = left + 1; i <= right; ++i)
        if (V[i - 1] > V[i]) {
            sorted = false;
            break;
        }
 
    int middle = (left + right) / 2;
    mergesort(left, middle);
    mergesort(middle + 1, right);
}
===

O calance a aprofundat acest algoritm si s-a decis sa faca urmatoarea optimizare: daca se apeleaza functia $MergeSort(i,j)$, iar sirul de la $i$ la $j$ este deja sortat, atunci functia sa se opreasca. Mai exact daca se apeleaza functia $MergeSort(i,j)$, aceasta sa continuie doar daca sirul NU este sortat.