Skip Navigation


The Computer Journal Advance Access originally published online on January 8, 2008
The Computer Journal 2008 51(4):451-469; doi:10.1093/comjnl/bxm097
This Article
Right arrow Full Text
Right arrow Full Text (PDF)
Right arrow All Versions of this Article:
51/4/451    most recent
bxm097v1
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Shutler, P. M. E.
Right arrow Articles by Lim, W. Y. S.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author 2008. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Analysis of Linear Time Sorting Algorithms

Paul M. E. Shutler*, Seok Woon Sim and Wei Yin Selina Lim

National Institute of Education, Nanyang Technological University, 1 Nanyang Walk, Singapore 637616, Republic of Singapore

* Corresponding author: paul.shutler{at}nie.edu.sg

Received 12 December 2006; revised 6 August 2007

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.

Key Words: linear time-sorting algorithms • cache latency • linear probing sort • bucket sort • Flashsort1 • radix sort • quicksort


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.