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);
}
(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?