CSC 482 HW3 — Language Comparison: Final Report

Algorithm: Randomized Quicksort (CLRS Ch. 5, RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION — Probabilistic Analysis and Randomized Algorithms, the unit's reading). Chosen because it ties directly to the unit content, has a well-known expected running time of O(n log n) to check the empirical curve against, and is simple enough to implement identically (in-place, Lomuto partition, uniformly random pivot swapped in before partitioning) in every language using only each language's standard library or toolchain (Rust's rand crate is the one standard, explicitly-allowed exception, since Rust's standard library has no built-in RNG).

Languages compared (15): C, C++, C#, Java, Python, Rust, Go, JavaScript, TypeScript, F#, Zig, Common Lisp, Pascal, x86-64 Assembly, PHP. The first 7 were the original comparison; the remaining 8 were added in a second round at the student's explicit request to push the comparison further (see §7 for which additional languages were requested but skipped, and why).

Machine: AMD Ryzen 7 5800H (8 cores / 16 threads, ~3.2 GHz base), 32 GB RAM, Windows 11 Pro host. All builds and all timed runs were executed inside WSL2 Ubuntu 26.04 ("Resolute Raccoon") for a consistent Linux environment across every language.

Method: each language has its own agent-implemented, independently-run benchmark under HW3/<lang>/, following the shared protocol in ../DESIGN.md: starting at n=1000, doubling n each iteration, generating a fresh random array each time (generation not timed), timing only the sort call with each language's standard high-resolution clock, and stopping when a single iteration exceeds 4.0s (the condition that actually ended every run here), 25 iterations elapse, or n would exceed 200,000,000. One call per n, no averaging — exactly as the assignment specifies is sufficient for a general trend.

1. Compliance check against HW3.docx

Bottom line: every technical requirement of the assignment is satisfied. The only remaining step is yours: actually submitting the folder's contents (and the PNG) to your course's dropbox and discussion topic by the due date.

2. AI-use disclosure (per your instructor's note that AI use is permitted if cited)

All code, benchmark harnesses, plots, and reports in this HW3/ folder were produced with the assistance of Claude (Anthropic), acting as an AI pair programmer per your explicit instructions (see ../instructions.txt) and per your instructor's stated policy allowing AI use as long as it's cited. You should carry a citation to this effect into your actual submission — e.g. a line in your write-up such as: "Code and analysis were developed with the assistance of Claude (Anthropic); the algorithm design (Randomized Quicksort) follows Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, Ch. 5."

3. Results

See all_results.csv for the combined machine-readable data (246 rows across 15 languages), and combined_plot.png / combined_plot_loglog.png / combined_plot_compiled_zoom.png for the graphs. Max n reached and time at that n per language, sorted fastest-at-max-n to slowest:

(TypeScript and JavaScript aren't directly comparable by "max n reached" the way the others are — both compile to/run as the same V8 JavaScript under Node, so their numbers track closely at every shared n; TypeScript's run happened to land just under the 4.0s cutoff at a smaller n and stopped one iteration earlier by chance, not because it's meaningfully different from plain JS. See §4 below.)

4. Discussion: does the curve match expected O(n log n)?

For a function that grows as Θ(n log n), doubling n should roughly double the runtime, with a small additional factor from the growing log term — the per-doubling ratio should sit a bit above 2.0 at small n and settle in toward ~2.0–2.3x as n grows large (since log₂(2n)/log₂(n) → 1 as n → ∞, the "extra" factor beyond a pure 2x shrinks slowly). That is almost exactly what every language's data shows once past the first few small-n iterations (which are dominated by timer resolution and one-time warmup costs, not the algorithm):

• C, C++, Rust, Go, Zig, Pascal, Assembly — the seven native-compiled languages (see combined_plot_compiled_zoom.png) — track each other closely (5.4–9.3s at n≈65.5M, six of the seven within 5.4–6.7s) and show clean, textbook per-doubling ratios in the ~2.0–2.3x range from roughly n=32,000 onward. This is the expected O(n log n) signature. Notably, the hand-written x86-64 Assembly did not beat gcc -O2 C (5.95s vs. 5.59s) — a modern optimizing compiler gives a naive integer quicksort little room to be beaten by hand, which is itself a reasonable finding to report, not a failure of the implementation (see reports/asm_report.md). Pascal is the slowest of the compiled cluster (9.29s) — FPC's default optimizer is simply less aggressive than GCC/LLVM/rustc's, a ~1.6x gap that's still very clearly in the "compiled language" performance class, not an order of magnitude off.
• C#, F#, Java all show the same asymptotic O(n log n) shape at large n, but with visible JIT/tiered-compilation noise at small-to-mid n — Java's report calls out non-monotonic timings from n=1,000–16,000 before the JIT settles into optimized code, and C#/F# (same runtime, same effect independently confirmed by both sibling reports) show a similar dip around n=1,024,000→2,048,000. These are real, expected managed-runtime effects (interpreter/JIT tiering + GC), not implementation bugs — F# in particular lands essentially identically to C# (5.87s vs. 6.44s at n=65.5M) since they share the same .NET runtime, as expected.
• Common Lisp (SBCL, which compiles to native code rather than interpreting) lands in a similar range to the managed-runtime languages (8.80s) despite being "compiled" — SBCL's report attributes this to a simpler/less aggressive optimizer than GCC/LLVM for this kind of workload, plus flags a real coarse-timer-resolution artifact at small n (several early readings rounded to exactly 0.000s) that's excluded from the growth-rate analysis but kept unfiltered in the CSV for transparency.
• PHP and Python are both interpreted, dynamically-typed languages and land where expected: PHP (with OPcache) is noticeably faster than Python — it reaches n=8,192,000 before hitting the 4.0s cutoff, 4x further than Python's n=2,048,000 — but still far behind every compiled/managed language, consistent with "interpreted but with some bytecode-caching optimization" being a real intermediate performance tier.
• JavaScript and TypeScript (both running as V8 JavaScript under Node — TypeScript compiles straight down to the same JS) are the most surprising result in the whole comparison: JavaScript's growth tracks O(n log n) cleanly through n=32,768,000, then jumps ~3.46x (instead of the expected ~2.2x) on the final doubling to 65,536,000, landing at 13.36s — the slowest single result in the entire 15-language comparison, even slower than Python at comparable n. The javascript_report.md attributes this to GC/memory-pressure effects specific to that array size rather than an algorithmic change (V8's JIT easily beats Python/PHP at every smaller n), but it's a genuine, reproducible measured anomaly worth calling out rather than smoothing over — a good illustration of the assignment's point that a single language's runtime "curve" is not always a clean textbook line in practice.
• Python shows the same O(n log n) shape internally (its own per-doubling ratios are consistent with the compiled languages' — see reports/python_report.md) but with a roughly 30–40x constant-factor penalty from CPython's interpreter overhead relative to the compiled languages: it hits the 4.0s cutoff at n=2,048,000, where every compiled language is still under 0.2s.

Taken together: every language's curve matches the expected O(n log n) asymptotic behavior of randomized quicksort (with JavaScript's one large-n anomaly noted above as a real, reported outlier rather than glossed over). The visible differences between languages are overwhelmingly constant-factor effects (compiled vs. interpreted, managed-runtime JIT/GC overhead, optimizer aggressiveness) rather than differences in algorithmic growth — exactly the distinction the assignment's prompt ("runtime is just one piece of the puzzle...") is pointing at. The full 15-language spread, fastest to slowest at n=65.5M (or each language's own max n), spans roughly 5.45s (C++) to 13.36s (JavaScript) among languages that reached large n, plus Python and TypeScript stopping at much smaller n under the same 4.0s budget — a single order of magnitude in per-operation cost separating a hand-optimized systems language from an interpreted dynamic one, which is a genuinely useful, concrete number for the "runtime is just one piece of the puzzle" discussion the assignment asks for.

5. Per-language detail

Full detail — exact compiler/runtime versions, RNG/pivot mechanics, external code citations, complete results tables, and language-specific anomaly notes — is in each language's own report:

• c_report.md
• cpp_report.md
• csharp_report.md
• java_report.md
• python_report.md
• rust_report.md
• go_report.md
• javascript_report.md
• typescript_report.md
• fsharp_report.md
• zig_report.md
• lisp_report.md
• pascal_report.md
• asm_report.md
• php_report.md

6. What's in this folder

HW3/
  DESIGN.md                  shared experiment protocol every language followed
                              (includes a "Round 2 languages" section covering the 8 added later)
  c/, cpp/, csharp/, java/, python/, rust/, go/,
  javascript/, typescript/, fsharp/, zig/, lisp/, pascal/, asm/, php/
                              source code + README.md (build/run instructions) per language
  results/
    <lang>.csv                per-language raw (n, time_seconds) data
    all_results.csv           combined data, all 15 languages (246 rows)
    make_plot.py               script that builds the combined CSV + all plots
    combined_plot.png          REQUIRED deliverable: linear-axis line graph, all 15 languages
    combined_plot_loglog.png   log-log view (much more legible across this 15-language, huge-n-range spread)
    combined_plot_compiled_zoom.png
                                zoom on the 7 tightly-clustered native-compiled languages
  reports/
    <lang>_report.md          per-language report (version, RNG method, citation, results, analysis)
    FINAL_COMPARISON.md        this file

7. Languages requested but not included, and why

The student asked to expand the comparison further, including several genuinely obscure or non-existent languages. None of the following were implemented, for the reasons given — none were silently skipped without explanation:

Not real, or no working modern toolchain exists at all: R++ (not a recognized programming language), PEARL (a 1970s–80s German industrial real-time language with no maintained Linux toolchain), Opal (dead academic language, unmaintained since the late 1990s), Mercury, Lucid, and Euler (historical/research languages with no working modern compiler found), Cobra (.NET-hosted language, last released ~2012, effectively abandoned). OpenCL was also excluded — it's a GPU-kernel framework hosted from C/C++, not a standalone language, and doesn't fit a "single function, timed on CPU" model without a substantial rewrite. NASM was not treated as a separate language slot — it's the assembler used to implement the Assembly entry.

Real and common, but skipped for this round: R, Prolog, Erlang, Elixir, Swift, and COBOL. None had apt packages available in this environment (its package mirror was missing many otherwise-standard packages, including ones as common as nasm and nodejs), so each would have required a substantial from-source bootstrap. That tradeoff became harder to justify after this same WSL environment's Linux-side state proved unreliable during setup of the 8 languages that were added — an idle-timeout was silently discarding installed packages between commands (worked around by setting vmIdleTimeout=-1 in .wslconfig), and one installed tool's own script file was found corrupted after being written (worked around by calling its underlying binary directly — both documented in ../DESIGN.md's "Round 2 languages" section). Given that instability, six more from-source builds was a poor time/risk tradeoff for a 15-point homework assignment that already covers 15 languages here — but they're all real, well-documented languages and could be added in a future round if you want to push further.

No GitHub repository or git history was created or touched anywhere in this project, per your instructions — everything lives locally in this folder, ready for you to zip up / copy into your dropbox submission.