C# Report — Randomized Quicksort (HW3)

Runtime / configuration

• Language: C#, .NET SDK 10.0.400 (confirmed via dotnet --version), target framework net10.0.
• Build configuration: Release (dotnet build -c Release -o bin/publish), 0 warnings / 0 errors.
• Executed inside WSL2 Ubuntu (distro Ubuntu), per HW3/DESIGN.md. The prebuilt native apphost couldn't locate the runtime in this WSL install (dotnet lives under /home/granite/.dotnet, outside the apphost's default search path), so the Release build was launched via dotnet ./bin/publish/HW3CSharp.dll instead of the apphost executable directly — this only changes the launcher, not the JIT/optimization behavior of the Release-built managed code being timed.
• CPU: 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 machine spec).

Random pivot / RNG

A single shared System.Random instance (Rng) is used for both:

1. Generating each iteration's test array (Rng.Next(0, 1_000_000) per element, n elements, not timed), and
2. Choosing the randomized pivot in RandomizedPartition(a, p, r): Rng.Next(p, r + 1) picks an index uniformly at random over the current subarray range [p, r]; that element is swapped into position r, and then the standard Lomuto Partition (CLRS PARTITION) runs against it. This mirrors CLRS's RANDOMIZED-PARTITION exactly.

External code

No external code used — original implementation based on CLRS's RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION pseudocode (Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, Ch. 5). Array.Sort/List.Sort were not used anywhere; the sort is implemented by hand with an in-place Lomuto partition.

Results

The loop ran for 16 iterations and stopped because the elapsed time of the n = 65,536,000 iteration (6.437 s) exceeded the 4.0 s cutoff (well before hitting the 25-iteration cap or the 200,000,000 next-n cap). Total wall-clock time for the whole run (process start to exit, via time) was 12.63 s.

Full data is also in HW3/results/csharp.csv.

Growth analysis

For n log n growth, doubling n should roughly multiply the running time by 2 * (log(2n) / log(n)), which for the n ranges here works out to roughly 2.0–2.3x per doubling. From n = 16,000 onward the observed ratios mostly sit in that 1.9x–2.3x band (e.g. 1.99x, 1.95x, 2.22x, 1.94x, 2.09x, 2.23x, 2.15x, 2.02x, 2.08x, 2.15x, 2.34x at the largest sizes), which is consistent with expected O(n log n) behavior for randomized quicksort. Two anomalies are worth calling out:

1. Small-n warm-up (n = 1,000–8,000): the first few iterations show noisier, sub-proportional or super-proportional ratios (1.27x, then a jump to 2.54x, then 1.35x) rather than the steady ~2x trend. This is the expected effect of .NET's tiered JIT compilation and general process warm-up — the earliest calls into RandomizedQuicksort/Partition run under the quick, less-optimized tier-0 JIT (or are still being JIT-compiled at all) before the runtime promotes hot methods to optimized tier-1 code, so timings for the smallest n are dominated by JIT/startup noise rather than genuine algorithmic cost, which is itself microseconds at this size.
2. n = 1,024,000 → 2,048,000 dip: time actually decreased slightly (0.1674s → 0.1415s, a 0.85x ratio) despite n doubling. This is the single clearest anomaly in the run. The most likely explanation is a combination of (a) tiered JIT promoting the sort/partition methods to fully optimized code around this point (a one-time step-function speed-up that can outweigh one doubling of n), and (b) run-to-run GC/scheduling noise from the .NET server/workstation GC doing a collection during the slower neighboring iterations. Aside from that one dip, growth from n = 2,048,000 up through n = 65,536,000 is smooth and consistently in the expected ~2.0x–2.35x per-doubling range, matching O(n log n) as expected for CLRS randomized quicksort.