[C++] Mergesort jak działa ten kod?

[mazix2]

Hej, mam takie pytanie - o dzialanie ponizszego kodu. Wiem, mniej wiecej, jak dziala mergesort, dzieli zboir na 2, potem kazdy z osobna sortuje i posortowane laczy ... Tylko ja jakos nie widze tego w tym kodzie (nie ja go pisalem, znalazlem w necie) moglby ktos dokladnie wytlumaczyc jak to dziala ?

Kod: Zaznacz cały

void merge(int* tab, int begin, int middle, int end)
{
    int i, s = middle, p = begin;
    int* tmp = new int[end];
    
    for(i = begin; i < end; ++i)
        tmp[i] = tab[i];
         
    i = begin;
    
    while(i < middle && s < end)
    {
     if(tmp[i] < tmp[s])
        tab[p++] = tmp[i++];
     else tab[p++] = tmp[s++];
    }
    
    while(i < middle)
          tab[p++] = tmp[i++];
}

void mergesort(int* tab, int begin, int end){
    if (begin < (end - 1))
    {
     int middle = (begin + end) / 2;
     mergesort(tab, begin, middle);
     mergesort(tab, middle, end);
     merge(tab, begin, middle, end);
    }

}

[LiTE]

http://pl.wikipedia.org/wiki/Sortowanie_przez_scalanie

Czytaj, jak nie rozumiesz czytaj jeszcze raz. Jak nie rozumiesz ponownie, to przeczytaj ponownie.
Zrób sobie przykład dla małej tablicy i posortuj, pooglądaj animacje dostępne w internecie.

[beluosus]

Polecam tę stronę http://www.sorting-algorithms.com/
Świetnie prezentacja popularnych algorytmów sortowania w działaniu dla różnego rodzaju danych wejściowych.