Why is the number of array accesses not considered in analyzing the complexity of mergesort?

Question

I'm reading Robert Sedgewick's Algorithms and in the section about The complexity of sorting, I found the following paragraph:

Proposition. Mergesort is an asymptotically optimal compare-based sorting algorithm. Proof: Precisely,we mean by this statement that both the number of compares used by mergesort in the worst case and the minimum number of compares that any compare-based sorting algorithm can guarantee are $\sim N\lg N$.

One analysis appears earlier in the book shows that mergesort uses $6N\lg N$ array accesses in the worst case and this number is $6$ times higher than the number of comparisons. And for large values of $N$, this would make a big difference between number of array accesses vs. number of compares. But still the model of computation only counts compares.

So why is the compare-based model of computation used here instead of access-based?

I'm aware of several related questions such as this one, but none seems to have answered my question.

Answer 1

To make our lives simpler, we often focus on the dominant operation for analyzing the running time of an algorithm. This laziness usually does not hurt us since we are mostly concerned with asymptotic analysis, where the constant coefficients and lower-order terms do not matter.

In the case of standard sorting algorithms, we primarily focus on two operations: number of comparisons required and number of swaps required. And not so surprisingly, number of comparisons is the dominant operation in this case.

The above argument only remains true under standard computational models, such as a RAM model. As soon as we are concerned with memory read/write complexity, we of course need to focus on the hidden constants under the asymptotic notations, such as $O$. Suppose we have two $O(n\log n)$ sorting algorithms, namely MergeSort and HeapSort. Once might be better than the other under a certain computational model, and the other way around in some other model. See here and here. External sorting algorithms are often concerned with access costs.

In most modern computing systems, having cache and predictive prefetching one of the bottlenecks is braching, which happens in the case of a comparison. Thus, it makes sense to focus on one of the most hurting operations compared to straight-forward memory access.

Researchers have been and are still continuing to come up with efficient sorting algorithms that serve better in special practical circumstances. See this paper for example.