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.
展开▼
机译：我们研究当键长k时确定基于最佳比较的原始排序的复杂性的问题不是常数。我们使用O（1）辅助数据位置在O（nk + n log n）时间内的第一种算法用于o（nk + n log n）时间，在时间和空间同时最佳。
展开▼
