The complexity of lexicographic sorting and searching
Applications of Mathematics, Tome 26 (1981) no. 6, pp. 432-436.

Voir la notice de l'article dans Czech Digital Mathematics Library

An asymptotically optimal sorting algorithm that uses $\Theta (n(log\ n+k))$ component comparisons to lexicographically sort the set of $n$ $k$-tuples is presented. This sorting algorithm builds the static data structure - the so called optimal lexicographic search tree - in which it is possible to perform member searching for an unknown $k$-tuple in at most $[(log_2(n+1)]+k-1$ comparisons. The number of comparisons used by this search algorithm is optimal.
DOI : 10.21136/AM.1981.103933
Classification : 68C25, 68E05, 68P10
Mots-clés : asymptotically optimal sorting algorithm; static data structure; lexicographic search tree 
@article{10_21136_AM_1981_103933,
     author = {Wiedermann, Juraj},
     title = {The complexity of lexicographic sorting and searching},
     journal = {Applications of Mathematics},
     pages = {432--436},
     publisher = {mathdoc},
     volume = {26},
     number = {6},
     year = {1981},
     doi = {10.21136/AM.1981.103933},
     mrnumber = {0634280},
     zbl = {0467.68057},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/articles/10.21136/AM.1981.103933/}
}
TY  - JOUR
AU  - Wiedermann, Juraj
TI  - The complexity of lexicographic sorting and searching
JO  - Applications of Mathematics
PY  - 1981
SP  - 432
EP  - 436
VL  - 26
IS  - 6
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/articles/10.21136/AM.1981.103933/
DO  - 10.21136/AM.1981.103933
LA  - en
ID  - 10_21136_AM_1981_103933
ER  - 
%0 Journal Article
%A Wiedermann, Juraj
%T The complexity of lexicographic sorting and searching
%J Applications of Mathematics
%D 1981
%P 432-436
%V 26
%N 6
%I mathdoc
%U https://geodesic-test.mathdoc.fr/articles/10.21136/AM.1981.103933/
%R 10.21136/AM.1981.103933
%G en
%F 10_21136_AM_1981_103933
Wiedermann, Juraj. The complexity of lexicographic sorting and searching. Applications of Mathematics, Tome 26 (1981) no. 6, pp. 432-436. doi : 10.21136/AM.1981.103933. https://geodesic-test.mathdoc.fr/articles/10.21136/AM.1981.103933/

Cité par Sources :