Iterative Quick Sort in PHP

<?php
declare(strict_types=1);
// Iterative Quick Sort in PHP
//
// PURPOSE
// Quick sort partitions around a pivot and sorts the two resulting regions. This iterative
// version stores pending intervals explicitly instead of using recursion.
//
// METHOD
// Choose a median-of-three pivot and partition into less-than, equal-to, and greater-than
// regions. Process the smaller region immediately and defer the larger one to keep the
// explicit stack bounded.
//
// COMPLEXITY
// O(n log n) average time, O(n squared) adversarial worst case. Equal-key input takes O(n).
// O(log n) pending intervals; 64 stack slots cover the supported bounded input lengths. Not
// stable.
//
// CONTRACT
// Sorts ascending in place and returns 0. Three-way partition handles repeated keys
// efficiently. Median-of-three reduces common fixed-endpoint pivot problems but does not
// provide introsort's worst-case guarantee.
// Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
// counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
// Sorted order, correct tree topology, and caller-owned data-structure invariants are
// preconditions; checking them on every query would change query complexity.
// Scalar and shape checks are included. Value-range checks are included where needed to
// prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
// workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
// uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
// partly updated after arithmetic failure. These are single-threaded, in-memory
// implementations.
//
// LANGUAGE DETAILS
// PHP 8.1+ on a 64-bit runtime: packed arrays, strict scalar types, read-only inputs by
// value using copy-on-write, references only for outputs, and checked 32-bit arithmetic.
// Invalid input and overflow throw exceptions. PHP arrays have higher overhead than native
// packed buffers in C/Java.
//
// EXAMPLE
// Expected return: 0.
// Expected a after call: [1, 1, 3, 5].
// Run: php example.php
// Tests for this exact source artifact run before publication. The accompanying source
// archive includes unit cases, runtime results, and source hashes.

function alg_require(bool $valid): void { if (!$valid) throw new InvalidArgumentException("invalid algorithm input"); }
function alg_checked(int|float $v): int { if ($v < -2147483648 || $v > 2147483647 || floor($v) != $v) throw new OverflowException("32-bit result overflow"); return (int)$v; }
function alg_add(int $a,int $b): int { return alg_checked($a+$b); }
function alg_sub(int $a,int $b): int { return alg_checked($a-$b); }
function alg_mul(int $a,int $b): int { return alg_checked($a*$b); }
function alg_size(int $n): int { alg_require($n>=0 && $n<=4000000); return $n; }

function quick_sort(array &$a): int {
    alg_require(array_is_list($a));
    $n = count($a);
    alg_require((($n >= 0) && ($n <= 1000000)));
    alg_require((count($a) == $n));
    $lefts = array_fill(0, alg_size(64), 0);
    $rights = array_fill(0, alg_size(64), 0);
    $top = 0;
    $low = 0;
    $high = alg_sub($n, 1);
    $left = 0;
    $right = 0;
    $mid = 0;
    $pivot = 0;
    $temp = 0;
    while ((($low < $high) || ($top > 0))) {
        if (($low >= $high)) {
            $top = alg_sub($top, 1);
            $low = $lefts[$top];
            $high = $rights[$top];
        }
        $mid = alg_add($low, intdiv(alg_sub($high, $low), 2));
        $pivot = max(min($a[$low], $a[$mid]), min(max($a[$low], $a[$mid]), $a[$high]));
        $left = $low;
        $mid = $low;
        $right = $high;
        while (($mid <= $right)) {
            if (($a[$mid] < $pivot)) {
                $temp = $a[$left];
                $a[$left] = $a[$mid];
                $a[$mid] = $temp;
                $left = alg_add($left, 1);
                $mid = alg_add($mid, 1);
            } else {
                if (($a[$mid] > $pivot)) {
                    $temp = $a[$mid];
                    $a[$mid] = $a[$right];
                    $a[$right] = $temp;
                    $right = alg_sub($right, 1);
                } else {
                    $mid = alg_add($mid, 1);
                }
            }
        }
        if ((alg_sub($left, $low) < alg_sub($high, $right))) {
            if ((alg_add($right, 1) < $high)) {
                $lefts[$top] = alg_add($right, 1);
                $rights[$top] = $high;
                $top = alg_add($top, 1);
            }
            $high = alg_sub($left, 1);
        } else {
            if (($low < alg_sub($left, 1))) {
                $lefts[$top] = $low;
                $rights[$top] = alg_sub($left, 1);
                $top = alg_add($top, 1);
            }
            $low = alg_add($right, 1);
        }
    }
    return 0;
}

$a = [5, 1, 3, 1];
$result = quick_sort($a);
echo $result, PHP_EOL;
echo json_encode($a), PHP_EOL;
// Expected a: [1, 1, 3, 5]