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
(from crpit.com)
(local if available)