44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03) An In-Place Sorting with O(n log n) Comparisons and O(n) Moves Cambridge, Massachusettes October 11-October 14 ISBN: 0-7695-2040-5
We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O(n log n) element comparisons and O(n) element transports. This solves a long-standing open problem, stated explicitly, e.g., in [J. I. Munro and V. Raman, Sorting with minimum data movement, J. Algorithms, 13, 374-93, 1992], of whether there exists a sorting algorithm that matches the asymptotic lower bounds on all computational resources simultaneously.
Citation:
Gianni Franceschini, Viliam Geffert, "An In-Place Sorting with O(n log n) Comparisons and O(n) Moves," focs, pp.242, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb