Sortowanie przez scalanie

Sama nazwa od razu nasuwa nam myśl, że będziemy coś łączyć... Ale my pracujemy na tablicy... Najpierw musimy ją podzielić. Cały algorytm opiera się na zasadzie dziel i zwyciężaj, ponieważ mniejszą tablice jest łatwiej posortować.
Dopóki tablica składa się z więcej niż jednego elementu, dzielimy ją na 2 połowy, oczywiste jest, że gdy tablica ma nieparzystą liczbę elementów to nie podzielimy środkowego elementu. Dlatego możemy go dodać np. do pierwszej połówki. Następnie rekurencyjnie powtarzamy dzielenie połówek na mniejsze części itd. Gdy każda część składa się tylko z 1 elementu scalamy posortowane części.
Scalanie polega na tym, że porównujemy pierwszy el. z części I z pierwszym el. z części II. Jeśli ten z części I był mniejszy to wstawiamy go do sklejonej tablicy na 1wszej pozycji... I następnie porównujemy 2gi el. z cz. I z pierwszym z części II. Tłumaczenie tego wygląda na trochę pogmatwane... Ale gdy spojrzycie na rysunek zasięgnięty z google to wyda się wam to łatwiejsze.