Zig — Randomized Quicksort Report (HW3)

Language / toolchain

• Zig 0.13.0 (official linux-x86_64 release tarball from ziglang.org).
• Built with zig build-exe quicksort.zig -O ReleaseFast (ReleaseFast optimization mode — the default Debug mode is unoptimized and was avoided).
• Run inside WSL2 Ubuntu on an AMD Ryzen 7 5800H (8 cores / 16 threads, ~3.2 GHz base), 32 GB RAM, Windows 11 Pro host (per HW3/DESIGN.md).

Algorithm / RNG

Implements CLRS's RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION directly:

• partition() is a standard Lomuto partition on arr[lo..hi] using arr[hi] as the pivot value.
• randomizedPartition() draws a pivot index uniformly at random from [lo, hi] (inclusive) via rand.intRangeAtMost(usize, lo, hi), swaps it into position hi, then calls partition() — this is CLRS's RANDOMIZED-PARTITION.
• randomizedQuicksort() recurses on the two resulting subarrays, matching RANDOMIZED-QUICKSORT.
• Sorting is entirely in-place on a []i32 slice; no calls to std.sort.* are made anywhere in the program.

RNG: a single std.Random.DefaultPrng (Zig's default PRNG, xoshiro256++), seeded once at program start from 8 bytes pulled out of std.crypto.random (the OS CSPRNG), is used for both purposes required by the harness:

1. generating each iteration's array of random test data (rand.intRangeLessThan(i32, 0, 1_000_000)), and
2. choosing the random pivot index at every partition step (rand.intRangeAtMost(usize, lo, hi)).

Data generation happens before the timer starts and is excluded from the measured time, per the harness spec.

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 third-party libraries; only the Zig standard library (std.Random, std.crypto.random, std.time.Timer, std.heap.page_allocator, std.fs, std.io, std.fmt) was used.

Results

Full results (also in HW3/results/zig.csv), n vs. time in seconds:

The run stopped after 17 iterations because the n = 65,536,000 iteration took 5.589 s, exceeding the 4.0 s cutoff (the 25-iteration and 200,000,000-n caps were not reached). Total wall-clock time for zig build-exe -O ReleaseFast plus the full harness run was ~11 seconds.

Growth analysis

The measured times track O(n log n) closely. Doubling n each iteration should roughly double the time, scaled up slightly by the growing log factor (2·log₂(2n)/log₂(n)); at these sizes (n ≈ 8M–65M, log₂n ≈ 23–26) that predicted ratio is about 2.08–2.09. The observed ratios between the last four consecutive doublings are 2.13, 2.07, 2.17, and 2.14 — right in that neighborhood, with the small excess plausibly explained by cache/TLB effects as the working set (up to ~256 MB for the n = 65,536,000 array of i32) outgrows L2/L3 cache at the largest sizes, plus ordinary timer-resolution and OS-scheduling noise at the very small end of the table (n = 1,000–8,000, where times are single-digit microseconds and dominated by call/loop overhead rather than the sort itself). No warmup, GC, or JIT effects are relevant here — Zig is ahead-of-time compiled to native code with no runtime or garbage collector, so there is no first-call interpretation or compilation cost to amortize; the very first iteration's time is already representative of steady-state performance.

As expected, Zig's results land essentially in the same performance class as the other AOT-compiled, manually-memory-managed systems languages in this comparison (C, C++, Rust): all four reach tens of millions of elements before hitting the 4 s cutoff, and their per-n timings are within a small constant factor of each other, consistent with all four compiling randomized quicksort down to similar native machine code with no managed-runtime overhead (no garbage collector, no bytecode interpretation, no bounds-checked-by-default array indexing in ReleaseFast mode). This is worth calling out explicitly since it's the expected outcome for a language occupying the same "compiled, manual memory management" niche as C/C++/Rust, in contrast to the managed/interpreted languages (Python, Java, C#, JavaScript, etc.) elsewhere in this comparison.