Попытка реализации алгоритма сортировки слиянием на пхп.

Увлекся я недавно изучением работы классических алгоритмов сортировки. Большинстов, конечно из них нетривиальны, но … платить за эффект нужно)…
На сколько я понял из прочитанного мною - 2 самых популярных это "слиянием"(на сколько знаю - он реализован во фреймворке джавы, это точно), ну и естественно, "быстрая сортировка", которая в качестве реализации в пхп для sort() и прочих была задействована.
А волнует в даной теме меня вот что… Я хотел на пхп протрассировать алгоритм слиянием, и… немогу корректно выполнить его… Я уже записал его вплоть до самых мелочей согласно псевдокоду, написанном в книге (Кормен и компания - "Алгоритмы. Построение и анализ"), да я вообще пробовал его реализовать по другому, но все безуспешно…

В чем проблема?
Сначала предоставлю сам код, а потом, как обычно постараюсь описать…

$input_arr = array(4,1,3,8,7,5,2,9,6);

function mergeSort($ar, $first, $last)
{
    if($first < $last)
        {
            $middle = floor( ($first+$last) / 2 );
            echo "first: ".$first."; last: ".$last."; middle: ".$middle."<br />";
            mergeSort($ar,$first,$middle);
            echo 'trying invoke mergeSort() for second part…<br />';
            mergeSort($ar,$middle+1,$last);
            echo 'trying invoke merge()…<br />';
            merge($ar,$first,$middle,$middle+1,$last);
        }
}

function merge($ar,$first1,$last1,$first2,$last2)
{
    $finalStart = $first1;
    $finalEnd = $last2;
    echo 'merge invoked…<br />';
    $c = 0;
    $temp = array();
    while($start1 <= $last1 && $start2 <= $last2)
        {
            if($ar[$start1] < $ar[$start2])
                {
                    $temp[$c] = $ar[$start1];
                    $start1++;
                }
                else
                    {
                        $temp[$c] = $ar[$start2];
                        $start2++;
                    }
                    $c++;
        }

        if($start1 <= $last1)
            {
                for($i = $start1; $i < $last1; $i++)
                    {
                        $temp[$c] = $ar[$i];
                    }
            }
            else
            {
                    for($i = $start2; $i < $last2; $i++)
                    {
                        $temp[$c] = $ar[$i];
                    }
            }

            $c = 0;

            for($i = $finalStart; $i< $finalEnd; $i++)
            {
                   $ar[$i] = $temp[$c];
                   $c++;
            }
}



mergeSort($input_arr,0,count($input_arr));

Результаты выполнения:

first: 0; last: 9; middle: 4
first: 0; last: 4; middle: 2
trying invoke mergeSort() for second part…
first: 3; last: 4; middle: 3
first: 3; last: 3; middle: 3
first: 3; last: 3; middle: 3
first: 3; last: 3; middle: 3
first: 3; last: 3; middle: 3
first: 3; last: 3; middle: 3
first: 3; last: 3; middle: 3
first: 3; last: 3; middle: 3
first: 3; last: 3; middle: 3
first: 3; last: 3; middle: 3

Вообщем, то что зацикливание по рекурсии, это понятно(хотя и не должно)… Это пол беды.
Но меня интересует не то. ПОЧЕМУ сначала впритык пополам делится первая часть массива (соответственно на этом основании для второй части и выходят неправильные данные)… И вообще, в следствии функция merge() даже не вызывается?
Насколько я понимаю, согласно теории(http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC)
все должно проходить по очереди. Тоесть сначала мы выбираем одним рекурсивным вызовом mergeSort() первую половину, а следующим - вторую, и только потом должна на этих основаниях вызыватся merge() чтобы посоиденять в отсортированном порядке две части.
Я пробовал реализовать по тому примеру что и на википедии(где пример на паскале), где рекурсивные вызовы присваиваются определенным переменным, но увы, результаты - те же(.

Почему рекурсия ведет себя таким образом? что я делаю неправильно?

p.s. Пожалуйста, не пишите чтото вроде "юзай sort() и парся с чем не надо". Просто исследую в учебных целях и ту теорию знать любому програмисту надо…

Naaayh, Да согласен…. ошибок насобирается пожалуй. Я просто этот алгоритм 7й раз гдето переписываю)….
я пробовал по разному передавать размеры. И так чтобы last был именно last а не размером массива, тоже.

mergeSort($input_arr,0,(count($input_arr) - 1));

И со ссилками чтобы явно массивы передавались - тоже. Вот, сейчас изменил….
результаты, увы, те же(… Хм… повела себя программа немного по-другому, когда изменил количество элементов на 8.
Мда, гемороя тут хватает… буду дальше штудировать)…

Вот переписан.

function mergeSort(&$ar, $first, $last)
{
    if($first < $last /*floor( ($first+$last) / 2 ) > 1*/)
        {
            $middle = floor( ($first+$last) / 2 );
            echo "first: ".$first."; last: ".$last."; middle: ".$middle."<br />";
            mergeSort($ar,$first,$middle);
            echo 'trying invoke mergeSort() for second part…<br />';
            mergeSort($ar,$middle+1,$last);
            echo 'trying invoke merge()…<br />';
            merge($ar,$first,$middle,$middle+1,$last);
        }
}

function merge(&$ar,$first1,$last1,$first2,$last2)
{
    $finalStart = $first1;
    $finalEnd = $last2;
    echo 'merge invoked…<br />';
    $c = 0;
    $temp = array();
    while($first1 <= $last1 && $first2 <= $last2)
        {   echo "first1: ".$first1."; first2: ".$first2."<br />";
            if($ar[$first1] < $ar[$first2])
                {
                    $temp[$c] = $ar[$first1];
                    $first1++;
                }
                else
                    {
                        $temp[$c] = $ar[$first2];
                        $first2++;
                    }
                    $c++;
        }

        if($first1 <= $last1)
            {
                for($i = $first1; $i < $last1; $i++)
                    {
                        $temp[$c] = $ar[$i];
                    }
            }
            else
            {
                    for($i = $first2; $i < $last2; $i++)
                    {
                        $temp[$c] = $ar[$i];
                    }
            }

            $c = 0;

            for($i = $finalStart; $i< $finalEnd; $i++)
            {
                   $ar[$i] = $temp[$c];
                   $c++;
            }

            echo "<pre>";
                print_r($ar);
            echo "</pre>";
}



mergeSort($input_arr,0,(count($input_arr) - 1));

Результаты:

Array
(
    [0] => 4
    [1] => 1
    [2] => 3
    [3] => 8
    [4] => 7
    [5] => 5
    [6] => 2
    [7] => 9
    [8] => 6
)
first: 0; last: 8; middle: 4
first: 0; last: 4; middle: 2
first: 0; last: 2; middle: 1
first: 0; last: 1; middle: 0
trying invoke mergeSort() for second part…
trying invoke merge()…
merge invoked…
first1: 0; first2: 1
Array
(
    [0] => 1
    [1] => 1
    [2] => 3
    [3] => 8
    [4] => 7
    [5] => 5
    [6] => 2
    [7] => 9
    [8] => 6
)
trying invoke mergeSort() for second part…
trying invoke merge()…
merge invoked…
first1: 0; first2: 2
first1: 1; first2: 2

……….

Вооьщем, видно, что рекурсия так и дальше замыкается с первого вызова сама в себя. И merge() при этом не вызывается…
first: 0; last: 8; middle: 4
first: 0; last: 4; middle: 2
first: 0; last: 2; middle: 1
first: 0; last: 1; middle: 0
…