How cache reckless quick look?

Question

In sorting letters, the author of the article claims that quick sorting is not a very efficient cache sorting algorithm. As the author noted

However, some of the shortcomings of quicksort are still present. Each character is checked several times until it is equal to the pivot partition. Each line is redirected every time a character in it is checked, and after the first split, these calls are effectively random. For a large set of lines, caching miss speeds are likely to be high.

I also found ppt that says quick sort and merge sort is Oblivious's cache code, but Wikipedia and a few papers claim that quick sort is very efficient in the cache.

I can not understand cases where fast sorting lost cache memory, except for the mandatory omission for integer data. Can someone explain a quick cache miss to skip in more detail?

Answer 1

The fragment quoted by you first of all speaks about problems at sorting of lines. If an array of strings during quicksort is stored as an array as pointers (which is basically the only simple way), then after the first pass of quicksort it is possible that pointers stored in adjacent positions in the array indicate memory located far from each other, even if the original array of strings was allocated in sequential memory. It seems plausible that sorting strings can be considered as a special problem, and specialized algorithms for it can be more efficient in the cache.

If instead you are sorting an array of, say, integers, then you are actually comparing and exchanging data in the array during quick sort, and therefore, when you access the nearest locations in the array, you will get the benefits of the cache. In this case, my understanding is the same as what you found on Wikipedia and elsewhere, namely, quicksort is quite efficient in the cache. This is mainly due to the fact that each quicksort pass processes its part of the array very locally.