Upper bounds for time-space trade-offs in sorting and selection (Q1101238)

Upper bound time-space trade-offs are established for sorting and selection in two computational models. For machines with input in read- only random access registers, and for machines with input on a read-only tape, we present algorithms that realize trade-offs of \(T\cdot S=O(N^ 2)\) for sorting and T log S\(=O(N \log N)\) for selection, where S is the number of workspace registers.