Cache Efficient Radix Sort for String Sorting
Waihong Ng, Kazuaki Kakehi · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2007
In this paper, we propose CRadix sort, a new string sorting algorithm based on MSD radix sort. CRadix sort causes fewer cache misses than MSD radix sort by uniquely associating a small block of main memory called the key buffer to each key and temporarily storing a portion of each key into its corresponding key buffer. Experimental results in running time comparisons with other string sorting algorithms are provided for showing the effectiveness of CRadix sort.