• Quicksort’s performance relies heavily on random variables

• We must measure its variance to understand its reliability

• To measure the fluctuation across multiple runs, we use the sample standard deviation formula:

Unlike Quicksort, Merge Sort’s execution is strictly deterministic.

• Consistent Partitioning: It always divides the dataset exactly in half, regardless of the initial array disorder.
• Minimal Algorithmic Variance: Because the number of operations is identical for any input of size \(N\), the algorithm’s internal variance is theoretically \(0\).
• Hardware Noise: Any minor fluctuations observed in runtimes will be due to hardware interference.
• The Trade-off: Statistical reliability comes at a hardware cost, requiring \(O(N)\) auxiliary memory for array allocations.

Holding the input size constant at \(N = 2,000\) across 100 independent runs on structured arrays reveals the true statistical spread of each algorithm.

To analyze how the algorithms scale, we programmatically loop through varying input sizes (\(N\)) and capture their execution distributions.

library(microbenchmark)

# define input sizes
sizes <- c(1000, 2000, 3000, 4000, 5000)
growth_df <- data.frame()

for (n in sizes) {
  test_array <- sample(1:n)
  
  # benchmark merge sort vs quick sort
  mb <- microbenchmark(
    merge_sort = merge_sort(test_array),
    quick_sort = quick_sort(test_array),
    times = 20 ) # 20 times per N
  
  # store results for visualization
  growth_df <- rbind(growth_df, data.frame(
    N = n, 
    Algorithm = mb$expr, 
    Time = mb$time / 1e6))
}

Merge Sort and Quicksort share an \(O(N \log N)\) average-case time complexity on randomized arrays, but Quicksort typically has a smaller constant factor, making it faster in practice.

library(plotly)
library(htmlwidgets)

sizes <- seq(1000, 3000, by = 500)
sorted_ratios <- seq(0, 1, by = 0.2)
plot_data <- data.frame()

for(n in sizes) {
  for(p in sorted_ratios) {
    num_sorted <- floor(n * p)
    random_part <- c()
    if (n - num_sorted > 0) {
      random_part <- (num_sorted + 1):n
      if (length(random_part) > 1) random_part <- sample(random_part)
    }
    test_arr <- c(if(num_sorted > 0) 1:num_sorted else c(), random_part)
    
    # run each algorithm 15 times and take the median to filter out OS noise
    t_merge <- median(replicate(15, system.time(merge_sort(test_arr))["elapsed"] * 1000))
    t_quick <- median(replicate(15, system.time(quick_sort(test_arr))["elapsed"] * 1000))
    
    plot_data <- rbind(plot_data, 
                       data.frame(N = n, Sortedness = p, Time = t_merge, Algorithm = "merge_sort"),
                       data.frame(N = n, Sortedness = p, Time = t_quick, Algorithm = "quick_sort"))
  }
}

p <- plot_ly(data = plot_data, x = ~N, y = ~Sortedness, z = ~Time, color = ~Algorithm, 
        colors = c("#8C1D40", "#FFC627"),
        type = "scatter3d", mode = "markers",
        marker = list(size = 6, opacity = 0.9),
        width = 700, height = 450) %>%
  layout(scene = list(
           xaxis = list(title = 'Input Size (N)'),
           yaxis = list(title = 'Ratio Sorted'),
           zaxis = list(title = 'Time (ms)')
         ),
         margin = list(l = 0, r = 0, b = 0, t = 0))

# save the plot independently (because it takes a while to generate)
saveWidget(p, file = "plotly_3d_isolated.html", selfcontained = TRUE)

As scale and sortedness increase, Merge Sort remains a predictable, flat plane, while Quicksort degrades sharply.

Rather than relying purely on Big-O notation and its implications, our benchmarking reveals how applying statistical analysis can provide a much clearer picture of an algorithm’s strengths and weaknesses.