tag

#cache-efficient

2 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 12. Specialized Search and Sorted-Order Procedures ›

Eytzinger Layout Search

Eytzinger Layout Search Eytzinger layout search reorganizes a sorted array into a breadth first tree layout, also known as heap order. The goal is to improve cache locality and make memory access patterns more predictable. Instead of storing data in sorted order, the array is rearranged so that binary search follows a sequential memory pattern. This reduces cache misses and improves throughput on modern CPUs. Problem Given a sorted array...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Cache Efficient Merge Sort

Cache Efficient Merge Sort Cache efficient merge sort improves merge sort by reducing cache misses. It reorganizes recursion and merging so that working data fits into cache levels. The goal is to minimize memory transfers rather than just comparisons. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le A[n-1] $$ while improving cache locality. Idea Standard merge sort performs well...