| Errata: | - Abstract, last sentence:
- multisets → sets
- Theorem 3:
- This theorem is weak since the contant α in
the n log2 n term may be larger than the constant 1 in the
∑i=1k ni log2 ni term. The result is only meaningful for
sets, not for multisets. We managed to provide a sorting algorithm
that is stable, runs in minimum space, and has optimal running time
for multisets in our 1994 paper "Sorting multisets stably in minimum
space" (Acta Informatica 31,4 (1994), 301–313).
|
HTML (Journal article)