### Analysing cache effects in distribution sortingAnalysing cache effects in distribution sorting

Access Restriction
Subscribed

 Author Rahman, Naila ♦ Raman, Rajeev Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2000 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Cache ♦ Efficient sorting algorithms ♦ External-memory algorithms ♦ Memory hierarchy Abstract We study cache effects in distribution sorting algorithms for sorting keys drawn independently at random from a uniform distribution ('uniform keys'). We note that the performance of a recently-published distribution sorting algorithm, Flashsort1, which sorts $\textit{n}$ uniform floating-point keys in $\textit{O(n)}$ expected time, does not scale well with the input size due to poor cache utilisation. We present an approximate analysis for distribution sorting uniform keys which, as validated by simulation results, predicts the expected cache misses of Flashsort1 quite well. Using this analysis, we design a multiple-pass variant of Flashsort1 which outperforms Flashsort1 and comparison-based algorithms on uniform floating-point keys for moderate to large values of $\textit{n}.$ Using experimental results we also show that the integer distribution sorting algorithm MSB radix sort performs well on both uniform integer and uniform floating-point keys. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2000-12-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 5

#### Open content in new tab

Source: ACM Digital Library