Go Report — HW3 Language Comparison

Language / runtime version

• Go 1.26.0 (go1.26.0 linux/amd64), confirmed via go version inside WSL2 Ubuntu.
• Build command: go build -o quicksort . (no special optimization flags — Go's default build is already an optimized, statically-linked binary; there is no separate debug/release mode to toggle as in C/C++/Rust).
• 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 (per DESIGN.md).

Random pivot / RNG

Random pivot selection and array generation both use the Go standard library math/rand/v2 package, specifically rand.IntN(k) to draw a uniform integer in [0, k). math/rand/v2's package-level generator is automatically seeded from a random source at process start, so no manual seeding was needed.

Pivot selection follows CLRS's RANDOMIZED-PARTITION exactly: at every call, randomizedPartition(a, lo, hi) picks pivotIndex := lo + rand.IntN(hi-lo+1) (uniform over the current subarray range [lo, hi]), swaps a[pivotIndex] and a[hi], then runs a standard Lomuto partition around a[hi]. This mirrors CLRS Ch. 5's RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION pseudocode.

External code

No external code used — original implementation based on CLRS RANDOMIZED-QUICKSORT/RANDOMIZED-PARTITION pseudocode (Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, Ch. 5). No sorting-library shortcuts (sort.Ints, slices.Sort) were called; the algorithm is implemented by hand in go/main.go.

Results

Full results (all 17 iterations recorded; loop stopped because the elapsed time for the n = 65,536,000 iteration exceeded the 4.0s cutoff):

(Also written to HW3/results/go.csv with header n,time_seconds.)

Stopping condition hit: elapsed time for the n = 65,536,000 iteration (6.709113s) exceeded the 4.0s cutoff, so the loop stopped after 17 iterations (well under the 25-iteration cap, and n never approached the 200,000,000 memory-safety cap).

Growth analysis

The observed timings match the expected O(n log n) growth well. Doubling n should roughly double the time and multiply it by an additional log(2n)/log(n) factor that slowly shrinks toward 1 as n grows, so the doubling ratio should sit a bit above 2.0 and drift only slightly. That is exactly what's seen here: the per-doubling ratio hovers in the ~1.9–2.2 range for most of the run (e.g. 128,000→256,000 is 2.10x, 1,024,000→2,048,000 is 2.07x, 4,096,000→8,192,000 is 2.01x), consistent with n log n rather than, say, n^2 (which would show ratios climbing toward 4x as n doubles). The smallest n values (1,000–8,000) show slightly noisier ratios (2.0x–2.1x) because the absolute times are tens to hundreds of microseconds, close to timer/scheduling noise and first-call effects (e.g. initial memory allocation for make([]int, n)), which is expected overhead rather than an algorithmic anomaly. At the largest sizes (16,384,000 → 65,536,000) the ratios creep up slightly to 2.15x, 2.17x, and 2.28x — a mild but real anomaly worth calling out. The most likely explanation is Go's garbage collector and memory subsystem: each iteration allocates a fresh []int slice (up to 512 MB at n = 65,536,000), and at that scale GC activity, page faults for newly touched memory, and reduced cache locality (the working set far exceeds L3 cache) all add measurable constant-factor overhead on top of the n log n trend, without changing its asymptotic shape. No JIT warmup effects apply here since Go compiles ahead-of-time to native code.