JavaScript (Node.js) Report - HW3 Language Comparison

Runtime / environment

• Runtime: Node.js v22.18.0 (official linux-x64 tarball from nodejs.org)
• Execution environment: WSL2 Ubuntu (distro Ubuntu), on an AMD Ryzen 7 5800H (8 cores / 16 threads, ~3.2 GHz base), 32 GB RAM, Windows 11 Pro host
• No compiler flags apply (JavaScript is JIT-compiled by V8 at run time; no special Node flags were passed - default invocation node quicksort.js)

Algorithm / RNG

Implements CLRS's RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION (Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, Ch. 5), in-place on a plain JS Array, using a Lomuto partition scheme:

• At every partition call over subarray [lo, hi], a pivot index is chosen uniformly at random from [lo, hi] via Math.random() (lo + Math.floor(Math.random() * (hi - lo + 1))).
• That pivot element is swapped into position hi (the last slot of the subarray), then a standard Lomuto partition runs, placing the pivot in its final sorted position and returning that index.
• The subarrays to the left and right of the pivot are recursively sorted.
• The same Math.random() source is also used to generate each iteration's input array (n random integers in [0, 1,000,000)), per the shared protocol - data generation is not timed.
• Array.prototype.sort is never called; the sort is implemented entirely by hand.

External code

No external code used - original implementation based on CLRS's RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION pseudocode. Only Node.js built-ins (fs, path) are used, for writing the CSV.

Timing harness

Followed the shared protocol in DESIGN.md exactly: n starts at 1000, a fresh random array of size n is generated (untimed) each iteration, only the call to randomizedQuicksort is timed using process.hrtime.bigint() (nanosecond-resolution monotonic clock), n doubles each iteration, and the loop stops when an iteration's elapsed time exceeds 4.0 s, 25 iterations have run, or the next n would exceed 200,000,000 - whichever comes first. Each sorted array is verified in-line (isSorted) before being accepted.

Results

The run stopped after 17 iterations (n = 65,536,000) because that iteration's elapsed time (13.36 s) exceeded the 4.0 s cutoff. Full data is also in results/javascript.csv. Total wall-clock time for the whole run (process startup + all 17 iterations) was about 26.6 s.

Growth analysis

For randomized quicksort, expected running time is O(n log n), so doubling n should roughly double the time and add a small extra factor from the log n term - the doubling ratio T(2n)/T(n) should trend toward 2 and slowly increase as log n grows (theoretically 2*(log n + 1)/log n). That is close to what's observed from n = 64,000 onward: ratios sit mostly in the 2.0-2.3 range (e.g. 0.0206/0.00997 ≈ 2.06 going from 128,000 to 256,000; 1.736/0.785 ≈ 2.21 going from 8,192,000 to 16,384,000), consistent with O(n log n) growth. Two anomalies are worth calling out:

1. Small-n noise / JIT warmup (n = 1,000 to 8,000): times are all sub-millisecond and actually decrease slightly through the first few iterations (0.000846s -> 0.000804s -> 0.000627s -> 0.000537s) before climbing again. This is the expected effect of V8's JIT: the interpreter runs the function's early (cold) calls, and V8's optimizing compiler (TurboFan) kicks in and produces faster machine code for partition/ randomizedQuicksort once they're "hot," which can make a slightly larger n finish faster than a smaller one purely from warmup timing, not algorithmic behavior. At these sizes the true sort work is a handful of microseconds, so timer/scheduler noise and warmup dominate the signal.
2. Final-iteration jump (n = 32,768,000 to 65,536,000): the ratio here is about 3.46x instead of the ~2.2x trend of the surrounding iterations. At 65.5 million doubles (~500+ MB for the array plus V8's object/array overhead), this array size is large enough to increase pressure on the V8 heap and trigger more/larger garbage-collection pauses and reduced CPU-cache locality during the sort, which plausibly explains the disproportionate slowdown rather than a change in the algorithm's asymptotic behavior.

Overall, the measured growth is consistent with the expected O(n log n) behavior for randomized quicksort once past the JIT-warmup noise at small n, with a plausible GC/memory-pressure anomaly at the largest n tested.