 | The ACM Journal of Experimental Algorithmics |
Volume 5, Article 14, 2000
Analysing Cache Effects in Distribution Sorting
by
and
http://www.jea.acm.org/2000/RahmanCache/
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 n uniform
floating-point keys in 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 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.
- Sources:
- The LaTeX version of the article;
this is a Unix file that contains the LaTeX source;
note that you must be a subscriber (institutional or individual) to access this file.
- The Postscript
version or PDF
version of the article;
note that you must be a subscriber (institutional or individual) to access
these files.
- The HTML version of the article;
note that you must be a subscriber (institutional or individual) to access
this file.
- The software suite accompanying the
article; this is a small Unix tar file, which includes the source code,
a Makefile, and the test files used in the article.
- The bibliography given in the article.
Received
|
Accepted
|
Final Revision
|
Published
|
|
|
|
|
Last updated and validated October 11, 2001, by editor@jea.acm.org