Comprehensive Empirical Benchmarking of Twelve Sorting Algorithms Across Comparison-Based, Non-Comparison-Based, and Hybrid Paradigms: A Multi-Dimensional Performance Model for Algorithm Selection at Practical Data Scales (n up to 100,000)

Abstract

This study extends the five-algorithm benchmark of Wibowo and Faisal [12] — which compared Heap, Shell, Merge, and Quick Sort against Python's built-in Timsort — to a twelve-algorithm framework spanning comparison-based, non-comparison-based, and hybrid/adaptive paradigms. Execution time (time.perf_counter()) and peak memory (tracemalloc) were measured across data sizes from 100 to 100,000 elements under random, ascending, and descending distributions, with stability and adaptivity empirically verified rather than only theoretically asserted. Results show that Counting Sort empirically breaks the Ω(n log n) comparison-sort lower bound under bounded key-range conditions, completing in 39.29 ms at n=100,000 versus 1,607.65–14,818.08 ms for the comparison-based algorithms tested (Mann-Whitney U test, p < 0.001). A key-range scaling experiment locates this advantage's precise boundary: it holds while the value range k remains at or below roughly 10 times n and inverts once k approaches 100 times n. Tim Sort remained the fastest overall algorithm (14.12 ms), while Bucket Sort's performance proved highly sensitive to its assumed value-range parameter, degrading toward quadratic behavior when that assumption diverged from the actual data range. All theoretical stability classifications were empirically confirmed, and a systematic rank-correlation analysis shows distribution sensitivity concentrated in adaptive algorithms' response to best-case ordering (ρ = 0.11–0.71 between random and ascending rankings) rather than in uniform reshuffling under any non-random input (ρ = 0.90–0.95 between random and descending rankings). The study contributes a reproducible, rule-based, multi-dimensional (time-space-stability-adaptivity) decision-support framework, presented as a decision-tree and rule table and checked, where independent data permits, against a held-out supplementary dataset, for algorithm selection at the moderate-to-large data scales tested here (n up to 100,000).