Cache-Friendly Sorting Techniques
What you'll learn: How to optimize sorting algorithms to work efficiently with modern CPU caches by minimizing slow memory accesses.
Why Cache Matters
Your CPU doesn't fetch data directly from RAM every time—it uses small, ultra-fast memory layers called caches (L1, L2, L3). When data is already in cache, access is 100x faster than fetching from main memory. When it's not (a "cache miss"), the CPU waits.
Think of it like organizing your desk: frequently used items stay within arm's reach (cache), while rarely used items sit in a filing cabinet across the room (RAM). The fewer trips you make to that cabinet, the faster you work.
What Makes Sorting Cache-Unfriendly?
Sorting algorithms that jump around memory unpredictably cause cache misses:
- Random access patterns (touching distant array elements)
- Poor spatial locality (not processing nearby elements together)
- Large working sets that don't fit in cache
Cache-Friendly Optimizations
1. Sequential Access
Process adjacent elements together. Mergesort naturally scans arrays sequentially during the merge phase—very cache-friendly.
2. Small Working Sets
Algorithms like Insertion Sort on small subarrays (in hybrid sorts like Timsort or Introsort) stay within cache since they operate on tiny chunks of data.
3. Blocking/Tiling
Break large arrays into cache-sized blocks, process each block completely before moving to the next. This keeps data "hot" in cache.
4. Prefetching Awareness
Modern CPUs predict access patterns and pre-load data. Sequential scans help this; pointer-chasing (like in some Quicksort implementations) hurts it.
Practical Impact
In-place Quicksort can suffer cache misses during partitioning when elements are far apart. Mergesort's sequential merge is cache-friendly but uses extra memory. Timsort balances both by using insertion sort for small runs (cache-friendly) and merging sequentially.
Key Takeaway: Cache-friendly sorting minimizes memory jumps by processing nearby elements sequentially, fitting working data into CPU caches, and choosing algorithms whose access patterns align with how modern hardware fetches data.