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, for example, in Munro and Raman [1992], of whether there exists a sorting algorithm that matches the asymptotic lower bounds on all computational resources simultaneously. © 2005 ACM.
An in-place sorting with O (n log n) comparisons and O(n) moves / Franceschini, Gianni; Viliam, Geffert. - In: JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY. - ISSN 0004-5411. - STAMPA. - 52:4(2005), pp. 515-537. [10.1145/1082036.1082037]
An in-place sorting with O (n log n) comparisons and O(n) moves
FRANCESCHINI, GIANNI;
2005
Abstract
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, for example, in Munro and Raman [1992], of whether there exists a sorting algorithm that matches the asymptotic lower bounds on all computational resources simultaneously. © 2005 ACM.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
