Measure the empirical operation counts (key comparisons and recursive depth) of Merge Sort, Quick Sort, and Heap Sort across datasets of size n from 64 to 4096 elements, verify the divide-and-conquer recurrence T(n) = 2T(n/2) + Θ(n) ⟹ Θ(n log₂ n), and extract the fundamental asymptotic scaling multiplier k_merge using ordinary least-squares linear regression. Explore interactive search algorithms, compare operation counts and analyse complexity scaling.
Ready to execute array size benchmark.
Adjust array size n, then execute benchmark.
Operation counts are generated deterministically by the exact algorithmic execution model. Modern hardware benchmarks additionally reflect cache line prefetching and branch misprediction penalties.
The theoretical RAM model assumes uniform constant-time O(1) access for every memory lookup and copy operation. On physical microprocessor architectures, Merge Sort's continuous memory allocation and copying between primary and auxiliary buffers incurs significant memory bus bandwidth saturation and cache-line evictions. Conversely, Quicksort's superior cache locality allows it to outpace Merge Sort in wall-clock time despite executing slightly more comparisons on average. Heap Sort eliminates auxiliary space completely but suffers severe cache misses due to non-local heap indexing strides. The theoretical worst-case key comparison count for Merge Sort on an array of size n = 2^k is exactly C(n) = n·log₂(n) − n + 1. Under ordinary least-squares regression against the recursive interval space x = n(log₂ n − 1), the theoretical slope is exactly k_merge = 1.0000 comparisons per interval, with an intercept of b = 1.0000 comparison and R² = 1.00000. In comparison, Quick Sort exhibits an average comparison count of C_avg(n) ≈ 2·n·ln(n) ≈ 1.386·n·log₂(n), running with superior cache locality and minimal constants, but suffers from an O(n²) worst-case on pathological pivot choices. Heap Sort achieves guaranteed O(n log n) execution strictly in-place with O(1) auxiliary space, but suffers higher constant factors due to irregular memory access strides.
Simulates a deterministic Von Neumann processor with register-level instruction counters, recording every atomic key comparison, pointer update, and stack frame activation without operating system thread jitter.
Allocates a contiguous block of virtual memory storing n 32-bit numerical keys, supporting constant-time O(1) random indexing for recursive partition boundaries.
Allocates an auxiliary scratchpad array of size n required by Merge Sort to perform linear-time reconciliation of sorted subarrays without in-place shifting penalties.
Maintains hardware cursors p1 and p2 traversing two adjacent sorted subarrays, performing ternary comparison to stream the lesser key into the destination buffer.
Monitors stack memory consumption and execution depth h = ⌈log₂ n⌉, tracking activation records (low, mid, high parameters) across the divide-and-conquer call tree.
Synthesizes uniform random permutations, pre-sorted arrays, reverse sequences, and pathological median-of-three killers to test algorithmic stability and worst-case bounds.
Measure the empirical operation counts (key comparisons and recursive depth) of Merge Sort, Quick Sort, and Heap Sort across datasets of size n from 64 to 4096 elements, verify the divide-and-conquer recurrence T(n) = 2T(n/2) + Θ(n) ⟹ Θ(n log₂ n), and extract the fundamental asymptotic scaling multiplier k_merge using ordinary least-squares linear regression. Suggested independent settings: 64, 128, 256, 512, 1024, 2048, 4096 elements.
Allocate the primary key array with n distinct integer keys for the chosen benchmark size n in [64, 128, 256, 512, 1024, 2048, 4096]. Allocate an identical auxiliary merge scratchpad of size n. Initialize the keys with a randomized permutation using the Knuth-Fisher-Yates shuffle algorithm.
Initiate the recursive divide phase. For subarray [low .. high], check base condition low >= high. If false, compute the overflow-safe midpoint mid = low + ⌊(high - low) / 2⌋. Allocate a new activation record on the call stack and recursively sort the left half [low .. mid] and right half [mid + 1 .. high].
When a subarray reaches size 1 (low == high), immediately terminate recursion with 0 comparisons. Unwind the stack frame to trigger the merging phase on the two returned sorted halves.
Initialize left cursor p1 = low and right cursor p2 = mid + 1. While p1 <= mid and p2 <= high, fetch A[p1] and A[p2] into ALU registers, increment the comparison counter C by 1, and copy the lesser (or equal) element into the auxiliary scratchpad. Advance the corresponding pointer.
Copy any remaining elements from the non-exhausted subarray directly into the scratchpad without additional comparisons. Copy the fully merged sequence from the auxiliary scratchpad back into the primary array buffer across indices [low .. high].
Upon return from the root invocation, record the total worst-case comparison count C_merge into the notebook. Repeat across all benchmark sizes n in [64, 128, 256, 512, 1024, 2048, 4096]. Compute x = n(log₂ n − 1) and perform ordinary least-squares regression to extract the scaling multiplier k_merge.
Points are your recorded benchmark observations. The regression line validates Divide-and-Conquer Sorting complexity scaling.
| # | Array size n (elements) (elements) | Key comparisons C_merge (comparisons) | Recursive interval space n(log₂ n − 1) (intervals) | Key comparisons C (operations) | Remove |
|---|
No readings yet. Execute a array size benchmark and record it.