How cache-oblivious is Quicksort?

Question

In Burst sort paper author claims that Quicksort is not very cache efficient sorting Algorithm. As author mentioned

However, some of the disadvantages of Quicksort are still present.Each character is inspected multiple times, until it is in an equal to pivot partition.Each string is re-accessed each time a character in it is inspected, and after the first partitioning these accesses are effectively random. For a large set of strings, the rate of cache misses is likely to be high.

I also found ppt which says quick sort and merge sort are cache Oblivious algorithm but Wikipedia and few paper claim that quick sort is very cache efficient.

I am not able to understand cases in which quick sort get cache miss apart from compulsory miss for integer data.Can anyone explain quick sort cache miss in detail ?

Answer 1

The passage you quoted is primarily talking about issues when sorting strings. If an array of strings during quicksort is stored as an array as pointers (which is basically the only easy way to do it), then after the first pass of quicksort it is possible that pointers stored in nearby positions in the array will point to memory locations that are far apart, even if the original array of strings was allocated in consecutive memory. It seems plausible that sorting strings can be treated as a special problem and specialized algorithms for it could be more cache efficient.

If instead you are sorting an array of, say, integers, then you are actually comparing and swapping around the data in the array during quicksort, and so when you access nearby locations in the array you will get cache benefits. In this case, my understanding is the same as what you found on wikipedia and elsewhere, namely, quicksort is fairly cache efficient. Basically this is because each pass of quicksort processes its portion of the array in a highly local fashion.