Sortowanie przez scalanie (MergeSort)

Sortowanie przez scalanie korzysta z metody "dziel i zwyciężaj", to znaczy dzielimy nasz problem na małe podproblemy, rozwiązujemy
każdy z nich i łączymy to znowu w jedną całość. Ale tak z polskiego na nasze, co konkretnie robimy??

Bierzemy jakąś nieposortowaną tablicę, np. 5, 2, 4, 7, 1, 3, 2 i 6. Teraz dzielimy ją na pół, otrzymujemy dwie takie tablice:
5, 2, 4, 7
1, 3, 2, 6

Teraz znowu dzielimy je na pół
5, 2
4, 7
1, 3
2, 6

I znowu
5
2
4
7
1
3
2
6

No i otrzymaliśmy 8 posortowanych tablic :) Bo w końcu jak jest tylko jedna liczba, to chcąc niechcąc jest ona posortowana.
No to teraz "scalamy" dwie sąsiednie, tzn, bierzemy 5 i 2 i układamy je do tablicy rosnąco, czyli wychodzi nam coś takiego:
2, 5
4, 7
1, 3
2, 6

Teraz znowu dwie sąsiednie, patrzymy na 2,5 i 4, 7, a skoro są posortowane, to patrzymy na pierwsze liczby w tablicach, czyli
porównujemy 2 i 4, wrzucamy mniejszą liczbę czyli 2 do tablicy, zostaje nam 5 i 4,7, porównujemy 5 i 4, wrzucamy 4, zostaje 5 i 7, porównujemy je i
otrzymujemy:
2, 4, 5, 7
1, 2, 3, 6

Teraz tą samą metodą scalamy pozostałe 2 tablice (porównując cały czas pierwsze liczby z każdej tablicy) i otrzymujemy:
1, 2, 2, 3, 4, 5, 6, 7

Obrazkowo można to przedstawić tak:

Co do kodu źródłowego, zamieszczam kod mojego autorstwa (na podstawie cormena), przy czym zakłada on, iż nie występują liczby większe od 10^9

Funkcja scal:

 (kod usunięty zgodnie z polityką publikowania)

I sortująca

void sortuj(int tab[], int p, int q)  //tab[] to tablica, p to początek, q to koniec
{
    if (p<q)
    {
        int r=(p+q)/2;   //dzielimy tablice na pół, jeśli początek jest wcześniej niż koniec ;)
        sortuj(tab, p, r);
        sortuj(tab, r+1, q);
        scal(tab, p, r, q);
    }
}