Python Report — HW3 Language Comparison

Language / runtime version

CPython 3.14.4 (confirmed via python3 --version inside WSL2 Ubuntu 26.04 "Resolute Raccoon"). No compilation step, no optimization flags — plain python3 quicksort.py invocation. No third-party packages used, standard library only (random, time, csv, os, sys).

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.randint(lo, hi) (Python's random module, Mersenne Twister-based PRNG, seeded automatically from OS entropy at interpreter start — no explicit seed was set). That element is swapped into position hi, and a standard Lomuto partition then runs around it. The same random module (random.randrange(0, 1_000_000)) is used to generate the input arrays for each iteration; data generation is not timed.

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/python' && python3 quicksort.py"

Loop stopped after 12 iterations because the measured time for n=2,048,000 (4.997s) exceeded the 4.0s cutoff (well before the 25-iteration or 200,000,000-element caps were reached — as anticipated in the assignment, Python's interpreter overhead means it stops far short of the memory-safety cap). Full results (also in ../results/python.csv):

Total wall-clock time for the whole run (including Python interpreter start-up and all 12 data-generation + sort iterations): ~10.5s (real from time python3 quicksort.py).

Growth analysis

For expected O(n log n) behavior, doubling n should multiply the running time by roughly 2 * (log2(2n) / log2(n)), which shrinks slowly from about 2.2x (near n=1,000, where log2(n)≈10) toward 2.0x as n grows into the millions (log2(n)≈21 at n≈2,048,000). The observed per-doubling ratios in this run range from about 1.99x to 2.57x, centered close to the theoretical band, with the last doubling (1,024,000 → 2,048,000) coming in at 1.99x — almost exactly the asymptotic 2x floor — and a few middling doublings (256,000 → 512,000 at 2.44x; 512,000 → 1,024,000 at 2.32x) running slightly above the pure-asymptotic prediction. This is consistent with expected O(n log n) growth for randomized quicksort; the modest excess in the mid-range doublings is plausible timing noise from CPython's per-call interpreter overhead (attribute lookups, bytecode dispatch, and list indexing inside the recursive randomized_quicksort/randomized_partition calls dominate the constant factor far more than in a compiled language, which flattens some of the log-factor curvature at smaller n) and possibly minor GC/memory-allocator effects as the list size crosses cache boundaries. No anomalies such as RecursionError occurred — recursion depth for randomized quicksort stays at O(log n) in expectation (≈21 for the largest n reached here), far under Python's default recursion limit, so sys.setrecursionlimit was never needed.