計算量O(n)の革命的なソートアルゴリズムをPHPでも

計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell - Qiita

スターリンソートは当然、PHPでも簡単に実装することができます。 https://3v4l.org/g9bR2

<?php

namespace stalin;

function sort(array $xs): array
{
    if (count($xs) <= 1) {
        return $xs;
    }

    $zs = $xs;
    $x = array_shift($zs);
    $y = array_shift($zs);

    if ($x <= $y) {
        return [$x, ...sort([$y, ...$zs])];
    }

    return sort([$x, ...$zs]);
}

動かしてみます。

echo json_encode(\stalin\sort([1, 2, 1, 1, 4, 3, 9]));
// [1,2,4,9]

完璧ですね。 PHP 7.3？ そんな古いバージョンのことは知りません

参考

• PHP: rfc:spread_operator_for_array

スターリンソートが流行ってるらしいので… https://t.co/5sor37Dl2D

— tadsan.exe (@tadsan) July 30, 2019