4
$\begingroup$

Introduction to Algorithms said that quicksort "works well even in virtual-memory environments," but didn't explain why. I've tried looking an Wikipedia and Stack Exchange, but found no reason why. Is it just because quicksort sorts in place?

$\endgroup$
5
$\begingroup$

The phrase in Cormen is a bit obscure (and does read a bit quaint). A 1978 paper by Sedgewick "Implementing Quicksort Programs" has a nutshell on this:

The hardware feature on modern computers that has the most drastic effect on the performance of algorithms is paging. Quicksort actually does not perform badly in a virtual memory situation (see [2]) because it has two slowly changing "localities" around the scanning pointers. In some situations, it will be wise to minimize page faults by performing the extra processing necessary to split the array into many partitions (instead of only two) on the first partitioning stage. Of course, the programs should be changed so that small subfiles are "insertionsorted" as they are encountered, because otherwise the last scan over the whole file will involve unnecessary page faults. Many internal sorting methods do not work well at all under paging, but Quicksort can be adapted to run quite efficiently.

The reference [2] cited there for further details is:

  • B.S., Gustavson, F.G., and Mankin, E. "Sorting in a paging environment." Comm. ACM 13, 8 (Aug. 1970), 483-494.

As it was suggested in the other answer, in more modern terms, the same property is phrased as quicksort having good cache locality; this is said for example in the 1994 paper "AlphaSort: A RISC Machine Sort" by Nyberg et al.; summary; the full text of this is found for example in Readings in Database Systems by Hellerstein and Stonebraker.

$\endgroup$
1
$\begingroup$

Data locality matters a lot with sorting algorithms.

http://betterexplained.com/articles/sorting-algorithms/

Look up "Cache Oblivious Algorithms" for more general principles relating algorithms to their ability to run well in the presence of caches.

$\endgroup$
  • $\begingroup$ I looked up "Cache Oblivious Algorithms," but it said no results were found. $\endgroup$ – Kelmikra Mar 4 '15 at 2:01
  • $\begingroup$ 1024cores.net/home/parallel-computing/… $\endgroup$ – Rob Mar 4 '15 at 2:51
  • 2
    $\begingroup$ This is correct, but how does it relate to virtual memory, that is why stress virtual? Also, links break; please at least summarize the text you link to. $\endgroup$ – Raphael Mar 4 '15 at 7:10
  • 1
    $\begingroup$ Virtual memory is an instance of caching. When you go to read virtual memory, it will get paged in and cached in physical memory on a miss, and when there is pressure to do so a page will be evicted from the physical memory cache and written out to disk. $\endgroup$ – Rob Mar 4 '15 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.