The Gateway to Computer Science Excellence
+3 votes
"Quick sort has good cache performance" , Can anyone explain this statement.How is cache related to quick sort.I searched for this over the internet but could not find a good article.
in Algorithms by | 515 views

3 Answers

+3 votes
Best answer

Quicksort is usually faster than sorts that are slower than O(nlogn) (say, Insertion sort with its O(n2) running time), simply because for large nn their running times explode.

A good reason why Quicksort is so fast in practice compared to most other O(nlogn)algorithms such as Heapsort, is because it is relatively cache-efficient. Its running time is actually O(n/Blog(n/B)), where B is the block size. Heapsort, on the other hand, doesn't have any such speedup: it's not at all accessing memory cache-efficiently.

The reason for this cache efficiency is that it linearly scans the input and linearly partitions the input. This means we can make the most of every cache load we do as we read every number we load into the cache before swapping that cache for another. In particular, the algorithm is cache-oblivious, which gives good cache performance for every cache level, which is another win


In addition, it’s very easy to avoid quicksort’s worst-case run time of O(n2)almost entirely by using an appropriate choice of the pivot – such as picking it at random (this is an excellent strategy).

selected by
+2 votes

quicksort changes the array inplace - in the array it is working on [unlike merge sort, for instance - which creates a different array for it]. Thus, it applies the principle of locality of reference.

Cache benefits from multiple accesses to the same place in the memory, since only the first access needs to be actually taken from the memory - the rest of the accesses are taken from cache, which is much faster the access to memory.

Merge sort for instance - needs much more memory [RAM] accesses - since every accessory array you create - is accessing the RAM again.

Trees are even worse - since 2 sequential accesses in a tree are not likely to be close to each other. [Cache is filled in blocks, so for sequential accesses - only the first byte in the block is a "miss" and the others are a "hit"].

+1 vote
I think one of the main reasons why Quick Sort is cache-friendly. When QS processes a segment of an array, it accesses elements at the beginning and end of the segment, and moves towards the center of the segment.

So, when you start, you access the first element in the array and a piece of memory (“location”) is loaded into the cache. And when you try to access the second element, it's (most likely) already in the cache, so it's very fast.

Other algorithms like heapsort don't work like this, they jump in the array a lot, which makes them slower.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,315 questions
60,428 answers
95,237 users