Sortarea prin interclasare

Sortarea prin interclasare împarte șirul în două, sortează fiecare jumătate, apoi le interclasează. Pentru $[5,2,4]$, partea $[5,2]$ se sortează în $[2,5]$, iar interclasarea ei cu $[4]$ dă $[2,4,5]$. Spre deosebire de interclasarea simplă, intrarea inițială nu trebuie să fie sortată: apelurile recursive pregătesc jumătățile.

Sortarea prin interclasare (mergesort) este tot o aplicație a metodei divide et impera. Segmentul [st, dr] se împarte la mijloc, m = (st + dr) / 2; se sortează recursiv cele două jumătăți, [st, m] și [m+1, dr], apoi ele se interclasează într-un tablou auxiliar și rezultatul se copiază înapoi. Un segment cu un element este deja sortat, deci recursivitatea se oprește la st >= dr. Spre deosebire de interclasarea simplă, intrarea nu trebuie să fie sortată: apelurile recursive pregătesc jumătățile. Adâncimea împărțirii este aproximativ ${\log }_{2}n$, iar pe fiecare nivel se interclasează în total $n$ elemente, deci timpul este $O(n\log n)$ în toate cazurile, indiferent de ordinea inițială. Memoria auxiliară este $O(n)$, pentru tabloul de interclasare. Dacă la egalitate se preia elementul din jumătatea stângă (<=), metoda este stabilă.

Exemplul 1 — tabloul $5,2,4$. Se împarte în $[5,2]$ și $[4]$. Jumătatea $[5,2]$ se împarte în $[5]$ și $[2]$, care se interclasează în $[2,5]$. Apoi $[2,5]$ și $[4]$ se interclasează: $2$, apoi $4$ (pentru că $4<5$), apoi $5$. Rezultatul este $[2,4,5]$.

#include <iostream>
using namespace std;
int a[100], aux[100];
void sortare(int st, int dr) {
    if (st >= dr) return;
    int m = (st + dr) / 2;
    sortare(st, m);
    sortare(m + 1, dr);
    int i = st, j = m + 1, k = st;
    while (i <= m && j <= dr)
        aux[k++] = (a[i] <= a[j] ? a[i++] : a[j++]);
    while (i <= m) aux[k++] = a[i++];
    while (j <= dr) aux[k++] = a[j++];
    for (int p = st; p <= dr; ++p) a[p] = aux[p];
}
int main() {
    a[0] = 5; a[1] = 2; a[2] = 4;
    sortare(0, 2);
    for (int i = 0; i < 3; ++i) cout << a[i] << " ";
    return 0;
}

Programul afișează 2 4 5.

Exemplul 2 — tabloul $5,2,4,1,3,6$. Primul apel împarte tabloul în $[5,2,4]$ și $[1,3,6]$. Prima jumătate se sortează ca mai sus și devine $[2,4,5]$; a doua, deja sortată, rămâne $[1,3,6]$. Interclasarea lor dă $[1,2,3,4,5,6]$. În total se fac 11 comparații în interclasări și se copiază înapoi 16 elemente.

Exemplul 3 — numărul de pași. Pentru $n=8$ elemente există ${\log }_{2}8=3$ niveluri de interclasare. Pe fiecare nivel se prelucrează 8 elemente, deci se copiază $3\cdot 8=24$ de elemente, indiferent dacă tabloul inițial este sortat, aproape sortat sau sortat invers. Atât pentru $8,7,6,5,4,3,2,1$, cât și pentru $1,2,3,4,5,6,7,8$ se fac 12 comparații, deoarece fiecare interclasare costă cât lungimea jumătății care se epuizează prima: $4\cdot 1+2\cdot 2+1\cdot 4=12$. Numărul de copieri rămâne 24. Pentru $n=1000$ sunt aproximativ $1000\cdot 10=10000$ de operații, față de aproximativ $500000$ la metodele cu $n^2$ pași.

Stabilitatea și alegerea metodei. La egalitate, condiția a[i] <= a[j] preia elementul din jumătatea stângă, deci două elemente egale rămân în ordinea inițială; cu < ordinea lor s-ar inversa. Pentru că timpul nu depinde de datele de intrare, metoda este potrivită când se cere un timp garantat sau o sortare stabilă; în schimb cere memorie suplimentară proporțională cu $n$, spre deosebire de sortarea rapidă și de cele trei metode simple, care sortează pe loc.

Exemplul 4 — urmărirea interclasărilor pentru $4,7,1,9,3,8,2,6$. Segmentul $[0,7]$ se împarte până la elemente izolate, iar interclasările se fac în ordinea în care apelurile recursive revin:

• $[0,1]$: $4,7$ dă $4,7$; $[2,3]$: $1,9$ dă $1,9$; apoi $[0,3]$: $4,7$ cu $1,9$ dă $1,4,7,9$;
• $[4,5]$: $3,8$ dă $3,8$; $[6,7]$: $2,6$ dă $2,6$; apoi $[4,7]$: $3,8$ cu $2,6$ dă $2,3,6,8$;
• $[0,7]$: $1,4,7,9$ cu $2,3,6,8$ dă $1,2,3,4,6,7,8,9$.

Se fac 17 comparații și 24 de copieri înapoi în tablou, adică $8\cdot 3$. Comparațiile depind de date (17 aici, 12 la un tablou sortat), copierile doar de $n$.

Greșeli frecvente

• Greșit: sortarea prin interclasare cere ca tabloul să fie sortat de la început.
  Corect: ea sortează tabloul oarecare; interclasarea se aplică jumătăților deja sortate de apelurile recursive.
• Greșit: este o metodă care sortează pe loc, fără memorie suplimentară.
  Corect: folosește un tablou auxiliar de dimensiunea segmentului, deci memorie $O(n)$.
• Greșit: timpul depinde puternic de ordinea inițială.
  Corect: este $O(n\log n)$ în toate cazurile.

Înainte și după