Analysis of Linear Time Sorting Algorithms

by: Paul M Shutler, Seok W Sim, Wei Y Lim

The Computer Journal, Vol. 51, No. 4. (1 July 2008), pp. 451-469.

View FullText article

DOI, HighWire

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

AbnerCYH

Find related articles with these CiteULike tags

algorithms, sys_performance

Abstract

We derive CPU time formulae for the two simplest linear time-sorting algorithms, linear probing sort and bucket sort, as a function of the load factor, and show agreement with experimentally measured CPU times. This allows us to compute optimal load factors for each algorithm, whose values have previously been identified only approximately in the literature. We also present a simple model of cache latency and apply it not only to linear probing sort and bucket sort, where the bulk of the latency is due to random access, but also to the log-linear algorithm quicksort, where the access is primarily sequential, and again show agreement with experimental CPU times. With minor modifications, our model also fits CPU times previously reported by LaMarca and Ladner for radix sort, and by Rahman and Raman for most significant digit radix sort, Flashsort1, and memory tuned quicksort. 10.1093/comjnl/bxm097

@article{citeulike:2945162, abstract = {We derive CPU time formulae for the two simplest linear time-sorting algorithms, linear probing sort and bucket sort, as a function of the load factor, and show agreement with experimentally measured CPU times. This allows us to compute optimal load factors for each algorithm, whose values have previously been identified only approximately in the literature. We also present a simple model of cache latency and apply it not only to linear probing sort and bucket sort, where the bulk of the latency is due to random access, but also to the log-linear algorithm quicksort, where the access is primarily sequential, and again show agreement with experimental CPU times. With minor modifications, our model also fits CPU times previously reported by LaMarca and Ladner for radix sort, and by Rahman and Raman for most significant digit radix sort, Flashsort1, and memory tuned quicksort. 10.1093/comjnl/bxm097}, author = {Shutler, Paul M. and Sim, Seok W. and Lim, Wei Y. }, citeulike-article-id = {2945162}, doi = {http://dx.doi.org/10.1093/comjnl/bxm097}, journal = {The Computer Journal}, keywords = {algorithms, sys\_performance}, month = {July}, number = {4}, pages = {451--469}, posted-at = {2008-06-30 16:05:54}, priority = {2}, title = {Analysis of Linear Time Sorting Algorithms}, url = {http://dx.doi.org/10.1093/comjnl/bxm097}, volume = {51}, year = {2008} }

RIS record

TY - JOUR ID - citeulike:2945162 L3 - citeulike-article-id:2945162 TI - Analysis of Linear Time Sorting Algorithms JF - The Computer Journal VL - 51 IS - 4 SP - 451 EP - 469 N2 - We derive CPU time formulae for the two simplest linear time-sorting algorithms, linear probing sort and bucket sort, as a function of the load factor, and show agreement with experimentally measured CPU times. This allows us to compute optimal load factors for each algorithm, whose values have previously been identified only approximately in the literature. We also present a simple model of cache latency and apply it not only to linear probing sort and bucket sort, where the bulk of the latency is due to random access, but also to the log-linear algorithm quicksort, where the access is primarily sequential, and again show agreement with experimental CPU times. With minor modifications, our model also fits CPU times previously reported by LaMarca and Ladner for radix sort, and by Rahman and Raman for most significant digit radix sort, Flashsort1, and memory tuned quicksort. 10.1093/comjnl/bxm097 KW - algorithms KW - sys_performance AU - Shutler, Paul AU - Sim, Seok AU - Lim, Wei PY - 2008/07/01/ UR - http://dx.doi.org/10.1093/comjnl/bxm097 ER -

RIS BibTeX