Quick sort and merge sort are two of the most prevalent comparison-based sorting algorithms. While both have their unique strengths and weaknesses, one of the most notable advantages of quick sort over merge sort is its superior cache locality. This article explores the technical aspects of how quick sort achieves better cache locality compared to merge sort, including examples, explanations, and relevant details.

Understanding Cache Locality

Cache locality refers to the use of data stored temporally in a cache to minimize memory access time. There are two main types of cache locality:

1. Temporal locality: The tendency to access the same memory locations repeatedly over a short period of time.
2. Spatial locality: The tendency to access a sequence of adjacent memory locations.

Efficient algorithms often leverage these principles to enhance performance, reducing cache misses and improving overall execution speed.

Quick Sort and Cache Locality

Quick sort is a divide-and-conquer algorithm. It works by choosing a 'pivot' element, partitioning the array into elements less than the pivot and elements greater than the pivot, and recursively sorting the subarrays.

Cache Locality Advantages

1. In-place Sorting: Quick sort is an in-place sorting algorithm, meaning it requires only a small, constant amount of extra storage, typically for recursive calls. This contrasts with merge sort, which requires additional space proportional to the size of the input array for temporary arrays during the merging step. The in-place nature of quick sort means better spatial locality because the data is manipulated directly within the existing array structure, reducing the need for additional memory allocation and minimizing cache misses.
2. Access Patterns: Quick sort tends to have superior cache-friendly access patterns. When partitioning and sorting subarrays, elements that are accessed are generally nearby, which enhances spatial locality. This means chunks of the data are used before moving on, which aligns well with the way cache lines work.
3. Pivot Selection and Recursion Depth: The choice of the pivot can impact cache performance. Although a poorly chosen pivot can degrade performance, modern implementations often use techniques such as median-of-three or randomization to optimize pivot selection, thereby leading to balanced partitioning and reducing the depth of recursion. A balanced partitioning keeps recursive operations within the bounds of cache lines.

Merge Sort and Cache Locality

Merge sort is also a divide-and-conquer algorithm, but it operates quite differently from quick sort. It works by dividing the array into two halves, recursively sorting each half, and then merging the two sorted halves back together.

Challenges with Cache Locality

1. Additional Memory Requirement: Merge sort requires auxiliary storage to accommodate the merging of sorted subarrays. The additional arrays typically do not exhibit good spatial locality since values from two separate subarrays are being accessed in tandem during the merge process. This can lead to increased cache misses.
2. Data Movement: During the merge step, two arrays are accessed in parallel, and a lot of data is moved between the input arrays and the auxiliary array. This movement breaks cache lines and reduces spatial locality efficiency.
3. Sequential Access: While merge sort does have good temporal locality with repeated accesses to array elements during merging, the fragmentation caused by auxiliary storage requirements tends to outweigh the benefits of sequential access patterns.

Table: Key Differences in Cache Locality

Conclusion

Quick sort's superior cache locality is primarily due to its in-place operations and cache-friendly access patterns, particularly when appropriate pivot selection strategies are employed. On the other hand, merge sort's reliance on auxiliary arrays and its data movement during merges tend to reduce cache efficiency.

Despite these differences, both quick sort and merge sort have their own merits and are suitable for different applications. Quick sort generally gives better performance with smaller auxiliary memory usage, especially when cache efficiency is a critical concern. However, due to its stable sorting property, merge sort still finds its place in scenarios where cache locality is less of a constraint.