Problem z MergeSort

[Alpha_PL]

Witam,
Obecnie na lekcjach przerabiamy funkcję rekurencyjną MergeSort. Przy czym podawana jest nam taka jego wersja.

Kod: Zaznacz cały

void MergeSort(int d[], int pocz, int kon)
{
  int sr;    [b] (1) [/b]  
  sr = (pocz+kon)/2;
 if (pocz<sr)               [b]   (2)[/b]
    MergeSort(d,pocz,sr);
  if (sr+1<kon) 
    MergeSort(d,sr+1,kon); [b](!)[/b]
  Merge(d,pocz,kon);
}

I wszysto przed (!) nie rozumiem. Wiem że polega to na takim czymś:
(1). Mamy np. zbiór 8-elementowy i dzielimy go na dwa 4-elementowe
(2).Potem te dwa podzbiory dzielimy też na dwa i robimy tak aż dostaniemy 8 podzbiorów jednoelementowych.

Funkcja Merge z tego co wyczytałem ma w tym momencie posortować dwa już posortowane podzbiory 4-elementowe. Ale czemu one są posortowane? Rekurencja MergeSort przecież podzieliła je na nie związane ze sobą jednoelementowe podciągi. Co je połączyło spowrotem w dwa 4-elementowe, posortowane zbiory?

[abc666]

Funkcja Merge() dla ciągów 4 elementowych zostanie odpalona dopiero na samym końcu. Wcześniej wejdziemy w rekurencje aż do ciągów dwu- lub jednoelementowych. Wtedy funkcja Merge() łączy je sortując. Potem wracamy mamy 2 pary ciągów dwuelementowych. Po połaszeniu mamy 2 ciągi 4 elementowe i wtedy jest odpalana funkcja Merge() na pierwszym poziomie.