Cache Efficient Radix Sort for String Sorting

Waihong NG  Katsuhiko KAKEHI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E90-A   No.2   pp.457-466
Publication Date: 2007/02/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e90-a.2.457
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
radix sort,  sorting,  cache,  string sorting,  high performance,  

Full Text: PDF(615KB)>>
Buy this Article

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.