Algorithmic Complexity and Cache Locality: Selection Sort vs. Quick Sort

ALGORITHMIC COMPLEXITY AND CACHE LOCALITY: SELECTION SORT VS. QUICK SORT Selecting an optimal sorting algorithm requires analyzing both mathematical time complexity (using Big-O notation) and physical hardware utilization. While Selection Sort has a time complexity of O(N squared) and Quick Sort exhibits an average case of O(N log N), their actual performance on physical CPUs is also heavily influenced by memory hierarchy and cache locality. TIME COMPLEXITY ANALYSES Selection Sort operates by scanning the unsorted portion of an array to locate the minimum value, performing a swap at most once per outer loop iteration. The comparison count is always N * (N - 1) / 2, resulting in a deterministic time complexity of O(N squared) for best, average, and worst cases. Quick Sort uses a divide-and-conquer strategy, selecting a pivot element and partitioning the array so that elements smaller than the pivot reside on the left, and larger elements reside on the right. If the partitioning is balanced, the recurrence relation resolves to T(N) = 2T(N/2) + O(N), yielding a time complexity of O(N log N). However, if the pivot selection is consistently poor (e.g., choosing the minimum or maximum element in an already sorted list), the partitioning degrades, resulting in a worst-case complexity of O(N squared). THE IMPACT OF SPATIAL LOCALITY Modern processors retrieve memory in fixed-size blocks called cache lines (typically 64 bytes) rather than individual words. Retrieving a value from RAM pulls adjacent values into the high-speed L1/L2 cache, establishing spatial locality. Quick Sort exhibits excellent spatial locality. The partitioning step scans the array sequentially from both ends towards the center. This sequential scanning pattern maximizes cache hits, as successive elements are already loaded into the CPU cache. Selection Sort, while performing fewer swaps (writes) than other quadratic sorts, requires scanning the entire unsorted array on every pass. For large datasets that exceed cache capacity, this constant full-array scanning results in frequent cache evictions and memory latency penalties. Therefore, Quick Sort's performance advantage over Selection Sort is not merely a consequence of performing fewer logical operations, but is also driven by its alignment with the memory hierarchy of modern processor architectures. Reference: Yang Hu, "Algorithms Python.pdf", Chapters 5 & 22: Select Sorting & Quick Sort.