asymptotically optimal sorting algorithm; static data structure; lexicographic search tree
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.
 R. L. Rivest: Partial-match retrieval algorithms
. SIAM J. Computing 5, 1976, pp. 115-174. MR 0395398
| Zbl 0331.68064
 J. van Leeuwen: The complexity of data organisation. Foundations of computer science II
. Part 1. Mathematical centre tracts 81, Mathematisch centrum, Amsterdam 1976. MR 0560287
 J. Wiedermann: Search trees for associative retrieval. (in Slovak). Informačné systémy 1, 1979, pp. 27-41.