gotchaMinor
Why does quicksort work well with virtual memory?
Viewed 0 times
whywithquicksortwellworkdoesmemoryvirtual
Problem
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?
Solution
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:
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.
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.
Context
StackExchange Computer Science Q#40039, answer score: 6
Revisions (0)
No revisions yet.