Rust Report — CSC 482 HW3 (Language Comparison)

Language / toolchain

• Rust, rustc 1.98.0 (88d9e12ae 2026-08-18), cargo 1.98.0 (797e8a9bc 2026-08-05), installed via rustup inside WSL2 Ubuntu.
• Built and run with cargo build --release (release profile: opt-level = 3, the default for --release) — confirmed release mode from the build output: Finished \release` profile [optimized] target(s) in 6.36s`.
• Executed via:

  wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/rust' && cargo build --release && ./target/release/quicksort"
  

• 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 (single-threaded workload; multiple cores available but unused by this program).

Algorithm / RNG

Implements CLRS's RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION (Ch. 5) directly:

• randomized_partition(a, p, r, rng) picks a pivot index uniformly at random from the inclusive range [p, r] via rng.gen_range(p..=r), swaps it into position r, then runs a standard Lomuto partition using a[r] as the pivot.
• randomized_quicksort drives this with an explicit stack of (p, r) subarray bounds (rather than recursive calls) so arbitrarily large n never risks stack overflow; behaviorally this is equivalent to the recursive RANDOMIZED-QUICKSORT pseudocode — the stack processes exactly the same left/right subproblems in place of a call stack.
• RNG: rand::thread_rng(), from the rand crate, seeded from the OS's secure entropy source. Used both for pivot selection (gen_range in randomized_partition) and for generating each iteration's fresh random input array (gen_range(0..1_000_000) in generate_random_vec), per DESIGN.md.
• No built-in sort (.sort()/.sort_unstable()) is called anywhere; sorting is done entirely by the hand-written randomized_quicksort/lomuto_partition functions.
• Data generation (generate_random_vec) is called before Instant::now() and is not included in the timed interval; only the call to randomized_quicksort is timed, using std::time::Instant.

External code used

• The rand crate (v0.8, resolved to v0.8.8), used purely for RNG (thread_rng()/gen_range). This is the standard, DESIGN.md-approved exception since Rust's standard library has no RNG.
• No other external code used — original implementation based on CLRS RANDOMIZED-QUICKSORT/RANDOMIZED-PARTITION pseudocode (Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, Ch. 5).

Results

Full results (also in HW3/results/rust.csv), 17 iterations, stopped when iteration 17 (n = 65,536,000) took 5.878s, exceeding the 4.0s cutoff:

Max n reached: 65,536,000, time 5.878s (this is the iteration that triggered the stop, per the >4.0s rule). Total wall-clock time for the whole run (build excluded, time around the binary invocation): ~12.08s real.

Growth analysis

For O(n log n) behavior, doubling n should roughly double the runtime times a slowly growing log factor — i.e., the ratio T(2n)/T(n) should be a bit above 2 and should trend slightly upward (or stay roughly flat) as n grows, converging toward 2 from above since log(2n)/log(n) → 1 as n → ∞. The observed per-doubling ratios in this run are consistently in the ~2.0–2.3x range across nearly the entire table (e.g., 8,000→16,000 is 2.08x, 128,000→256,000 is 2.10x, 1,024,000→2,048,000 is 2.05x, 4,096,000→8,192,000 is 2.04x), which matches expected O(n log n) growth well — a pure O(n) algorithm would show ratios flat at ~2.0x, while O(n^2) would show ratios near 4.0x; the data sits just above the linear line, consistent with the extra log n factor. The two smallest transitions (n=1000→2000 at 2.37x and n=2000→4000 at 1.85x) are the main anomaly and are attributable to measurement noise at microsecond scale — timer resolution, one-time allocator/OS page-fault warmup on the first few Vec allocations, and CPU frequency ramp-up, all of which have outsized relative effect when the timed interval itself is only tens of microseconds. No other anomalies (no GC, no JIT in Rust) were observed; the largest iterations show smooth, consistent scaling right up to the 4-second cutoff.