The Implication of O(n log n) Sorting Algorithms on Distributed Parallelism Through Memory Locality and Cache Hierarchies in Heterogeneous Computing Systems

While the asymptotic complexity of merge sort is well-understood as Θ(n log n), this abstraction obscures several critical practical considerations that become paramount at extreme scale. Specifically, we must consider cache line sizes (typically 64 bytes on modern x86 architectures) and how they interact with pointer-based versus array-based data structures during the divide-and-merge phase of a parallel radix sort implementation running across multi-tenant cloud instances where noisy neighbors can induce unpredictable L3 cache contention. Furthermore, in distributed systems using MPI for cross-node communication, the network topology matters enormously: an all-to-all shuffle operation exhibits different performance characteristics on fat trees versus 2D torus interconnects due to bisection bandwidth constraints. I am particularly interested in whether anyone has empirical data on when switching from a parallel merge sort to a distributed radix sort becomes beneficial given specific data distributions, as the theoretical crossover point is often dominated by constant factors that asymptotic analysis conveniently ignores. Let me know your thoughts and any benchmarks you have run.

This is a genuinely interesting angle because everyone keeps pushing for O(1) or whatever parallel reduction you can cram into a thread, but nobody talks about what actually happens at the cache level when you scale across heterogeneous nodes. The real bottleneck in distributed quicksort isn't the comparison count — it's that partition steps generate non-local memory access patterns that absolutely murder L3 performance and make NUMA coherency traffic the dominant term. If your data doesn't fit a single node, O(n log n) is already doing more work than the asymptotic notation suggests because of all those cache misses during the partitioning phase.

I worked on something similar last year for a time-series processing pipeline and switched to a radix sort variant that

good thread

The real interesting angle isn't just the O(n log n) bound — it's that you can't actually achieve a lower asymptotic complexity for comparison sorting, which means any speedup in distributed systems comes from constant factors, and

Interesting read, thanks for sharing.