PHP Report — HW3 Language Comparison

Language / runtime version

PHP 8.5.4 (cli) (NTS), Zend Engine v4.5.4 with Zend OPcache v8.5.4 (confirmed via php --version inside WSL2 Ubuntu 26.04 "Resolute Raccoon"), installed via the apt package php (one of the few round-2 languages actually available through apt in this environment). No compilation step, no optimization flags — plain php quicksort.php invocation. Standard library / core built-ins only (random_int, mt_rand, hrtime, fopen/fwrite/fflush/fclose).

Machine: AMD Ryzen 7 5800H (8 cores / 16 threads, ~3.2 GHz base), 32 GB RAM, Windows 11 Pro host, benchmark executed inside WSL2 Ubuntu.

Random pivot / RNG

Randomized pivot selection follows CLRS RANDOMIZED-PARTITION: at every partition call on subarray a[lo..hi], a pivot index is drawn uniformly at random from [lo, hi] via random_int($lo, $hi) (PHP's CSPRNG-backed random integer function, seeded automatically by the engine — no explicit seed was set). That element is swapped into position hi, and a standard Lomuto partition then runs around it (see partition() in php/quicksort.php). Input arrays for each iteration are generated with mt_rand(0, 999999) (Mersenne Twister-based PRNG); data generation is not timed — only the call to randomizedQuicksort() is timed, using hrtime(true) for nanosecond-precision monotonic timing. No built-in sort()/usort() is used anywhere in the sorting logic.

External code used

No external code used — original implementation based on CLRS RANDOMIZED-QUICKSORT/RANDOMIZED-PARTITION pseudocode (Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, Ch. 5).

Results

Run via:

wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/php' && php quicksort.php"

Loop stopped after 14 iterations because the measured time for n=8,192,000 (8.240982s) exceeded the 4.0s cutoff (well before the 25-iteration or 200,000,000-element caps were reached). Full results (also in ../results/php.csv):

Total wall-clock time for the whole run (including PHP interpreter start-up and all 14 data-generation + sort iterations): ~16.3s (real from time php quicksort.php).

Growth analysis

For expected O(n log n) behavior, doubling n should multiply the running time by roughly 2 * (1 + 1/log2(n)), which shrinks from about 2.20x near n=1,000 (log2(n)≈10) down toward about 2.09x at n≈8,192,000 (log2(n)≈23). The observed per-doubling ratios in this run range from about 1.95x (first doubling, 1,000→2,000, likely dominated by measurement noise/timer resolution at such a small workload) up to about 2.19x, with most doublings from 128,000 onward clustering tightly in the 2.05x–2.19x band — squarely consistent with the theoretical prediction. This matches expected O(n log n) growth for randomized quicksort well; the small deviations at the low end are consistent with fixed per-call overhead (function-call dispatch, array bounds/type checks) dominating the true n log n term when n is tiny, an effect that fades as n grows and the asymptotic term takes over. As anticipated in the assignment notes, PHP's interpreted, dynamically-typed nature places it between the managed-runtime languages (Java/C#, which JIT-compile hot code) and a purely interpreted language like Python — PHP reached roughly 4x the max n that Python reached (8,192,000 vs. 2,048,000) before hitting the same 4s cutoff, and at comparable n (e.g. ~2,048,000) PHP's ~1.73s is noticeably faster than Python's ~5.0s, consistent with Zend Engine/OPcache's more efficient bytecode dispatch and array (hash table) implementation relative to CPython's. No anomalies such as stack overflows occurred — recursion depth for randomized quicksort stays at O(log n) in expectation (≈23 for the largest n reached here), far under any practical PHP call-stack limit, so no xdebug.max_nesting_level or stack-size adjustments were needed.