Cache Analysis of Non-uniform Distribution Sorting Algorithms

Details Cache Analysis of Non-uniform Distribution Sorting Algorithms Cache Analysis of Non-uniform Distribution Sorting Algorithms

2007-06-19

arxiv.org/abs/0706.2839v2

Computer Science

Data Structures and Algorithms

The full version of our ESA 2000 paper (LNCS 1879) on this subject

Scientific paper

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)$.

Affiliated with

Also associated with

No associations

Rating

Cache Analysis of Non-uniform Distribution Sorting Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Cache Analysis of Non-uniform Distribution Sorting Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache Analysis of Non-uniform Distribution Sorting Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-281915