Conferences in Research and Practice in Information Technology
  

Online Version - Last Updated - 20 Jan 2012

 

 
Home
 

 
Procedures and Resources for Authors

 
Information and Resources for Volume Editors
 

 
Orders and Subscriptions
 

 
Published Articles

 
Upcoming Volumes
 

 
Contact Us
 

 
Useful External Links
 

 
CRPIT Site Search
 
    

Rotated Library Sort

Lam, F. and Wong, R.K.

    This paper investigates how to improve the worst case runtime of INSERTION SORT while keeping it in-place, incremental and adaptive. To sort an array of n elements with w bits for each element, classic INSERTION SORT runs in O(n2) operations with wn bits space. GAPPED INSERTION SORT has a runtime of O(n lg n) with a high probability of only using (1+_)wn bits space. This paper shows that ROTATED INSERTION SORT guarantees O(p n lg n) operations per insertion and has a worst case sorting time of O(n1:5 lg n) operations by using optimal O(w) auxiliary bits. By using extra _(pn lg n) bits and recursively applying the same structure l times, it can be done withO(2ln1+1l ) operations. Apart from the space usage and time guarantees, it also has the advantage of efficiently retrieving the i-th element in constant time. This paper presents ROTATED LIBRARY SORT that combines the advantages of the above two improved approaches.
Cite as: Lam, F. and Wong, R.K. (2013). Rotated Library Sort. In Proc. Theory of Computing 2013 (CATS 2013) Adelaide, Australia. CRPIT, 141. Wirth, A. Eds., ACS. 21-26
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS