| Optimal In-Place Sorting of Vectors and Records (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. We study the problem of determining the complexity of optimal comparison-based in-place sorting when the key length, k, is not a constant. We present the first algorithm for lexicographically sorting n keys in O(nk+n log n) time using O(1) auxiliary data locations, which is simultaneously optimal in time and space. 1 | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||