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.
Optimal in-place sorting of vectors and records / Franceschini, Gianni; Roberto, Grossi. - STAMPA. - 3580:(2005), pp. 90-102. (Intervento presentato al convegno ICALP tenutosi a Lisbon; Portugal) [10.1007/11523468_8].
Optimal in-place sorting of vectors and records
FRANCESCHINI, GIANNI;
2005
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.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
