Cache Analysis of Non-uniform Distribution Sorting Algorithms
| dc.creator | Rahman, Naila | |
| dc.creator | Raman, Rajeev | |
| dc.date | 2007-06-19 | |
| dc.date | 2007-08-13 | |
| dc.date.accessioned | 2026-07-07T08:23:01Z | |
| dc.date.available | 2026-07-07T08:23:01Z | |
| dc.description | We analyse the average-case cache performance of distribution sorting algorithms in the case when keys are independently but not necessarily uniformly distributed. The analysis is for both `in-place' and `out-of-place' distribution sorting algorithms and is more accurate than the analysis presented in \cite{RRESA00}. In particular, this new analysis yields tighter upper and lower bounds when the keys are drawn from a uniform distribution. We use this analysis to tune the performance of the integer sorting algorithm MSB radix sort when it is used to sort independent uniform floating-point numbers (floats). Our tuned MSB radix sort algorithm comfortably outperforms a cache-tuned implementations of bucketsort \cite{RR99} and Quicksort when sorting uniform floats from $[0, 1)$. | |
| dc.description | The full version of our ESA 2000 paper (LNCS 1879) on this subject | |
| dc.identifier | https://arxiv.org/abs/0706.2839 | |
| dc.identifier | http://arxiv.org/abs/0706.2839 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/135846 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Performance | |
| dc.title | Cache Analysis of Non-uniform Distribution Sorting Algorithms | |
| dc.type | text |