HW3 — Java Report: Randomized Quicksort

Language / runtime

• Language: Java
• Compiler/runtime: OpenJDK 25.0.4 (build 25.0.4+7-1-26.04-Ubuntu), OpenJDK 64-Bit Server VM, mixed mode, tiered JIT compilation (C1 + C2), confirmed via java --version inside WSL2 Ubuntu 26.04.
• Optimization flags: none passed explicitly (javac Main.java, java Main). The HotSpot JVM's default tiered JIT compilation and default heap sizing were used as-is — no -Xmx, -XX:+UseXXX, or -server/-client flags.
• 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.

Random pivot / RNG

A single java.util.Random instance (RNG, default no-arg constructor — seeded from system entropy/nanoTime internally by the JDK) is used for both:

• Data generation: RNG.nextInt(1_000_000) per array element, producing values uniform in [0, 1_000_000).
• Pivot selection: in randomizedPartition(a, p, r), the pivot index is i = p + RNG.nextInt(r - p + 1), which is uniform over the current subarray range [p, r] inclusive — matching CLRS RANDOMIZED-PARTITION. The chosen element is swapped to position r and then a standard Lomuto PARTITION is run.

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 calls (Arrays.sort/Collections.sort) are used anywhere in java/Main.java.

Results

Full results (also in HW3/results/java.csv):

16 iterations ran. The loop stopped after n = 65,536,000 because that iteration's elapsed time (7.808886121 s) exceeded the 4.0 s cutoff (the next-n-would-exceed-cap and 25-iteration conditions were not yet reached). Total wall-clock time for the whole run (compile excluded, JVM startup plus all 16 sort iterations, time java Main) was ~15.2 seconds.

Growth analysis

The observed growth is consistent with the expected O(n log n) behavior. For an O(n log n) algorithm, doubling n should roughly double the running time, scaled up slightly by the log(2n)/log(n) factor (e.g. around 2.1x-2.4x for n in the millions, converging toward 2x asymptotically). From n = 32,000 onward the measured per-doubling ratios are consistently in the ~1.8x-2.5x range (e.g. 32,768,000 -> 65,536,000 is a 2.35x increase for a 2x increase in n, and 512,000 -> 1,024,000 is a 2.49x increase), matching that expectation well, and the timings scale smoothly and monotonically for all n >= 32,000.

The smallest n values (1,000 through 16,000) show the expected anomalies rather than clean O(n log n) scaling: n=1000 (0.64 ms) is actually slower than n=2000 (0.28 ms), and n=8000 -> n=16000 shows almost no increase (0.87 ms -> 0.94 ms). This is the classic JIT warmup effect — the JVM starts in interpreted/C1 mode and only promotes hot methods (partition, randomizedPartition, randomizedQuicksort, nextInt) to optimized C2-compiled native code after enough invocations, which for such small arrays happens mid-run rather than before the first timed call. At these sub-millisecond durations, System.nanoTime() measurements are also more susceptible to OS scheduling jitter and background JVM activity (e.g. class loading, GC bookkeeping) than to the algorithm's actual asymptotic cost, so the first several data points are noisy by nature. By n = 32,000 and beyond, JIT compilation has stabilized and the measured growth tracks the theoretical O(n log n) curve closely, with no GC-pause anomalies visible in the larger-n timings despite arrays up to 65,536,000 ints (~262 MB) being allocated and sorted each iteration.