Does partition function gives quick sort its locality of reference?

Question

Does partition function gives quick sort its locality of reference ? If it does, how ?

I mean what is there in quicksort which gives it locality of reference when compared to other algorithms such as merge sort or heap sort ?

I also read that

"The partitioning step in quicksort typically has excellent locality, since it accesses consecutive array elements near the front and the back".

i did not get it ?

Dominy

Answer 1

In general, code has good locality of reference if the memory accesses it makes tend to be sequentially located around a small number of areas of memory. For example, linear search over an array has great locality of reference because all the elements appear adjacent in memory, but linear search over a linked list has poor locality because the linked list cells don't necessarily appear consecutively in memory.

Let's take a look at quicksort. The "meat" of the quicksort algorithm is the partitioning step, where elements are rearranged around a pivot. There are several strategies for implementing the partition algorithm, most of which have excellent locality. One common approach works by scanning inward from the ends of the array toward the center, swapping elements whenever they're relatively out of place. This algorithm keeps most of the array accesses confined to two regions - the ends of the array - and accesses elements sequentially, so it has great locality.

Another partitioning strategy works by scanning from the left of the array to the right, storing two pointers delimiting the regions holding the smaller values and the greater values. Again, the array accesses are all sequential, so the locality is really good.

Now, contrast that with heapsort. In heapsort, the heap operations require you to repeatedly compare elements at one position with elements whose index is twice or half the index of that element. This means that the array accesses are scattered across the array rather than sequential, so the overall locality is a lot worse.

Mergesort actually has somewhat decent locality due to how the merge step works. However, because it maintains an auxiliary buffer array that's as large as the input array, it has to pay the cost of extra memory and its accesses are therefore a bit more scattered than quicksort's accesses.

Solicitous

Merge sort has very similar LOR as to Quick Sort, right? – Petition

@Petition My recollection is that it doesn't actually have the best locality. If you look at the scans that quicksort does, each scan made recursively starts and stops roughly at the spots where its subcalls begin scanning, whereas mergesort doesn't preserve locality from call to call. Mergesort also pays a bit more for the auxiliary array. That said, I might be totally wrong about this - though I suspect this is correct and explains why quicksort typically runs much faster. – Solicitous

Answer 2

'Locality of reference' refers memory accessed frequently(temporal locality) or contiguous memory locations(spatial locality) as in array. Basically, it means that the machine(more specifically, cache memory) finds it easier, and therefore faster, to access these memory locations.

Consider the merge sort algorithm.
It first(virtually) divides the array into half up to the smallest unit i.e. singular elements(split function). It then compares arrays two-at-a-time and merges them in a sorted manner(merge function). Consider a sample merge b/w two arrays of length n, say, arr[0]...arr[n-1] and arr[n]...arr[2n-1]. The processor has to fetch first elements of both arrays, i.e. arr[0] and arr[n]. Since they are not localized, it will be less efficient.

Compare this with the Quick Sort algorithm.
Every comparison in the partition function takes place among adjacent i.e. localized memory locations, thus it will be cache efficient.

Hope this helps!

Vickivickie