F# Report — Randomized Quicksort (HW3)

Runtime / configuration

• Language: F#, .NET SDK 10.0.400 (confirmed via dotnet --version), target framework net10.0.
• Project scaffolded with dotnet new console -lang F# -o . (produces fsharp.fsproj / Program.fs).
• Build configuration: Release (dotnet build -c Release -o bin/publish), 0 warnings / 0 errors.
• Executed inside WSL2 Ubuntu (distro Ubuntu), per HW3/DESIGN.md. As with the C# sibling, the prebuilt native apphost isn't reliably resolved by 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/fsharp.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. F# and C# both compile to the same IL and run on the same CoreCLR/JIT, so the two languages are directly comparable at the runtime level.
• 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 via Array.init n, 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. The sort works in place on a mutable int[], updated via direct index assignment (a.[i] <- ...) inside swap/partition — the standard, idiomatic way to express an in-place algorithm in F# even though the language is functional-first.

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/Array.Sort were not used anywhere; the sort is implemented by hand with an in-place Lomuto partition, written independently of the C# sibling implementation (mutable-array/index-assignment style rather than a translation of the C# source, and using F# idioms such as Array.init for data generation and rec/pattern-free recursive functions for the quicksort calls).

Results

The loop ran for 17 iterations and stopped because the elapsed time of the n = 65,536,000 iteration (5.8701539 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) was 11.72 s.

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

Growth analysis

For O(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 band (1.99x, 2.00x, 2.10x, 1.90x, 2.02x, 2.07x, 2.08x, 2.00x, 2.38x, 1.94x, 2.33x), which is consistent with expected O(n log n) behavior for randomized quicksort. Two anomalies are worth calling out, both of the same character seen in the C# sibling run (same CoreCLR/JIT underneath):

1. Small-n warm-up (n = 1,000–8,000): the first few ratios are noisy relative to the steady ~2x trend seen at larger sizes — 1.74x, then 2.21x, then a dip to 1.16x — rather than a smooth progression. This is the expected effect of .NET's tiered JIT compilation and general process warm-up: the earliest calls into randomizedQuicksort/partition execute under the quick, less-optimized tier-0 JIT (or are still being compiled at all) before the runtime promotes the hot methods to fully optimized tier-1 code, so timings at these sizes are dominated by JIT/startup noise rather than genuine algorithmic cost (which is itself only tens of microseconds at this size).
2. n = 512,000 → 1,024,000 near-flat step: time barely changed (0.0926556s → 0.0914453s, a 0.99x ratio — essentially no growth despite n doubling). This is the clearest anomaly in the run, directly analogous to the dip the C# sibling saw one step later (at n = 1,024,000 → 2,048,000). The most likely explanation is tiered JIT promoting the sort/partition methods to fully optimized code around this point (a one-time step-function speed-up from tier-0 to tier-1 code that can momentarily outweigh one doubling of n), combined with run-to-run GC/scheduling noise. Aside from that one flat step, growth from n = 2,048,000 up through n = 65,536,000 is smooth and consistently in the expected ~2.0x–2.4x per-doubling range, matching O(n log n) as expected for CLRS randomized quicksort.