Question regarding the asymptotic complexity of O(n log n) sorting algorithms under specific degenerate input distributions and their real-world performance implications on modern hardware cache hierarchies

I find myself pondering a question that has been gnawing at me for several days, and I would genuinely appreciate your collective expertise here because this is something I can't quite wrap my head around with the level of rigor required. We all know the textbook definitions: Timsort achieves O(n log n) in the worst case through its clever use of runs and merge logic, Quicksort averages O(n log n) but hits O(n^2) on sorted or reverse-sorted data without a good pivot strategy, and Heapsort is strictly O(n log n) everywhere. But I'm thinking about what happens when we move beyond the asymptotic abstraction into actual silicon with real cache lines and branch predictors. Consider a scenario where the input isn't random but has structure — say, nearly-sorted segments of approximately equal length that are themselves randomly ordered relative to each other. Timsort would recognize the runs and perform extremely well because its merge logic is designed precisely for pre-existing order. But what about Quicksort? If we use a median-of-three pivot strategy (which most modern std::sort implementations do), how close does it get to O(n^2) in this specific hybrid case compared to the theoretically bad worst case? I've run some benchmarks on my workstation and observed that for n=10^7 with 40% pre-sorted segments, Timsort beats Quicksort by roughly a factor of three even though both are O(n log n). This suggests that the constant factors hiding in the big-O notation are doing enormous amounts of actual work. Now let me extend this to cache effects: Heapsort has terrible locality because its heap operations jump around memory addresses unpredictably, which means on modern CPUs with L1/