algorithm - How Cache Oblivious quick sort is? -

in burst sort paper author claims quick sort not cache efficient sorting algorithm. author mentioned

however, of disadvantages of quicksort still present.each character inspected multiple times, until in equal pivot partition.each string re-accessed each time character in inspected, , after first partitioning these accesses random. large set of strings, rate of cache misses high.

i found ppt says quick sort , merge sort cache oblivious algorithm wikipedia , few paper claim quick sort cache efficient.

i not able understand cases in quick sort cache miss apart compulsory miss integer data.can explain quick sort cache miss in detail ?

the passage quoted talking issues when sorting strings. if array of strings during quicksort stored array pointers (which easy way it), after first pass of quicksort possible pointers stored in nearby positions in array point memory locations far apart, if original array of strings allocated in consecutive memory. seems plausible sorting strings can treated special problem , specialized algorithms more cache efficient.

if instead sorting array of, say, integers, comparing , swapping around data in array during quicksort, , when access nearby locations in array cache benefits. in case, understanding same found on wikipedia , elsewhere, namely, quicksort cache efficient. because each pass of quicksort processes portion of array in highly local fashion.