Алгоритм поиска и сортировки PHP: Strand sort

Алгоритм поиска и сортировки PHP: упражнение 15 с решением

Напишите программу PHP для сортировки списка элементов с использованием сортировки Strand.

Это способ сортировки чисел путем извлечения более коротких последовательностей уже отсортированных чисел из несортированного списка.

Пример решения:

PHP-код:

<?php
$lst = new SplDoublyLinkedList();
foreach (array(100, 0, 2, 5, -1, 4, 1) as $v)
    $lst->push($v);
foreach (strandSort($lst) as $v)
    echo "$v ";
echo " ".PHP_EOL;
function strandSort(SplDoublyLinkedList $lst) {
    $result = new SplDoublyLinkedList();
    while (!$lst->isEmpty()) {
        $sorted = new SplDoublyLinkedList();
        $remain = new SplDoublyLinkedList();
        $sorted->push($lst->shift());
        foreach ($lst as $item) {
            if ($sorted->top() <= $item) {
                $sorted->push($item);
            } else {
                $remain->push($item);
            }
        }
        $result = _merge($sorted, $result);
        $lst = $remain;
    }
    return $result;
}
function _merge(SplDoublyLinkedList $left, SplDoublyLinkedList $right) {
    $res = new SplDoublyLinkedList();
    while (!$left->isEmpty() && !$right->isEmpty()) {
        if ($left->bottom() <= $right->bottom()) {
            $res->push($left->shift());
        } else {
            $res->push($right->shift());
        }
    }
    foreach ($left as $v)  $res->push($v);
    foreach ($right as $v) $res->push($v);
    return $res;
}
?>

Пример вывода:

 -1 0 1 2 4 5 100 

Блок-схема:

Редактор кода PHP:

Есть другой способ решить это решение? Внесите свой код (и комментарии) через Disqus.

Предыдущий: Напишите программу PHP для сортировки списка элементов, используя сортировку Bogo.
Далее: Напишите программу PHP для сортировки списка элементов, используя сортировку Patience.