Есть вопрос по функции mergesort.

[Just]

Есть вот такое задание:

на странице по ссылке
http://algolist.manual.ru/sort/merge_sort.php
расписан алгоритм сортировки слиянием
Ваше задача:
Создать Массив на 1000 элементов заполнит его случайными значениями от 1-1000
и используя описанный алгоритм отсортировать его в порядке возрастания.
Я сделал такой код:

Код:

function mergesort($array, $beg, $end) {
    if (count($array) < 1) return;
    else
    {
    $split = count($array) / 2;

    $array1 = array_slice($array, $beg, $split);

    $array2 = array_slice($array, $split + 1, $end);
    sort($array1);
    sort($array2);
    }
    $array = array();
    $ptr1 = $ptr2 = 0;
    while ($ptr1 <= count($array1) && $ptr2 <= count($array2)) {
        if ($array1[$ptr1] < $array2[$ptr2]) {

           $array[] = $array1[$ptr1++];
        }
        else {
            $array[] = $array2[$ptr2++];
        }
    }


while ($ptr1 < count($array1)) $array[] = $array1[$ptr1++];
while ($ptr2 < count($array2)) $array[] = $array2[$ptr2++];
return $array;
    }



$beg = 1;
$end = 1000;
$ar = array();
/* заполнение массива случайными числами, вариант первый: */
for($i = 1; $i <= 1000; $i++)
{
$ar[] = $i;
shuffle($ar);
}
/*вариант второй:
$ar = array();
for($i = 1; $i <= 1000; $i++)
{
$ar[$i] = rand(1, 1000);
}
*/
echo "Sorted massiv:";
echo '<br><br>';
$sorted = mergesort($ar, $beg, $end);
foreach($sorted as $val)
{
 echo $val; echo '<br><br>';
}

мне пришел ответ:
Переработайте скрипт без использования стандартных функций sort, array_slice, используя созданую Вами функцию
mergesort (используя рекурсию) Обратите внимание на использование минимального количества памяти сделать замер.

Я не знаю как это сделать помогите кто чем сможет. Заранее спасибо!

[Just]

Я попробовал переделать функцию mergesort, таким образом:

Код:

function mergesort(&$array, $beg, $end) {
    if (count($array) < 2) return;
    else
    {
    $split = count($array) / 2;

    $array1 = array_slice($array, $beg, $split);

    $array2 = array_slice($array, $split + 1, $end);

    mergesort($array1, $beg, $split);
    return $array1;
    mergesort($array2, $split+1, $end);
    return $array2;
    }
    $array = array();
    $ptr1 = $ptr2 = 0;
    while ($ptr1 <= count($array1) && $ptr2 <= count($array2)) {
        if ($array1[$ptr1] < $array2[$ptr2]) {

           $array[] = $array1[$ptr1++];
        }
        else {
            $array[] = $array2[$ptr2++];
        }
    }


while ($ptr1 < count($array1)) $array[] = $array1[$ptr1++];
while ($ptr2 < count($array2)) $array[] = $array2[$ptr2++];
return $array;
    }

возвращается не отсортированный массив. Каким образом вызвать ее рекурсивно и передать правильные параметры не могу понять.

[Sla]

что это?

mergesort($array1, $beg, $split);
return $array1;

mergesort($array2, $split+1, $end);
return $array2;

[Just]

mergesort($array1, $beg, $split); - вызов самой себя рекурсивно, с передачей параметров для сортировки(сам сортируемый массив, его левая граница и правая).
return $array1; - возврат отсортированного массива, обратно в вызывающую функцию.
Во втором случае тоже самое.

скорее всего это неправильно, я просто сам не знаю как вызвать эту ф-цию рекурсивно.

[McZim]

Рекурсия.

PROGNAME=$0
дальше по тексту
$PROGNAME

[Sla]

ну ты вызвал функцию
потом ретёрн
а потом второй раз вызываешь
а ретёрн уже прошел

[Just]

я просто не знаю как сделать возврат из рекурсивной ф-ции. Поэтому и написал этот ретерн.
Если сделать вот так:

Код: (PHP)

function mergesort(&$array, $beg, $end)
{
        if (count($array) < 2)
                return;
        else
        {
                $split = count($array) / 2;

                $array1 = array_slice($array, $beg, $split);
                $array2 = array_slice($array, $split + 1, $end);

                mergesort($array1, $beg, $split);
                mergesort($array2, $split+1, $end);
        }

        $array = array();
        $ptr1 = $ptr2 = 0;

        while ($ptr1 <= count($array1) && $ptr2 <= count($array2))
        {
                if ($array1[$ptr1] < $array2[$ptr2])
                {
                        $array[] = $array1[$ptr1++];
                }
                else
                {
                        $array[] = $array2[$ptr2++];
                }
        }

        while ($ptr1 < count($array1))
                $array[] = $array1[$ptr1++];

        while ($ptr2 < count($array2))
                $array[] = $array2[$ptr2++];

        return $array;
}

возвращается пустой массив.

Переформатировал код в более читаемый вид.

[McZim]

Just, почитай вообще про рекурсию.

[RXL]

Just, у нас есть хорошие статьи о рекурсии:

Тут: https://club.shelek.ru/view.php?id=25

https://club.shelek.ru/viewart.php?id=184
https://club.shelek.ru/viewart.php?id=205
https://club.shelek.ru/viewart.php?id=220
https://club.shelek.ru/viewart.php?id=226

[Just]

Спасибо большое за помощь! Обязательно почитаю статьи.