Improving counting sort algorithm via data locality
Shamsed Mahmud, Sardar Anisul Haque, Nazim Choudhury · 2022
In this paper, we proposed a cache-friendly hybrid sorting algorithm that combined a non-comparison sorting algorithm (counting sort) with a comparison sort (quick sort) algorithm. The current study leverages the principle of locality to improve the performance of the counting sort algorithm over a large list of integer inputs. We employed a modified version of the original quick sort algorithm to reduce the number of cache misses in counting sort. We also empirically tested the performance of the proposed hybrid algorithm by varying both the range and the quantity of the input values. This hybrid approach not only demonstrated a superior performance over the classic counting sort algorithm but also is capable of facilitating parallelism that was impractical for the classic counting sort algorithm.