A model of computation is introduced which permits the analysis of both the time and space requirements of non-oblivious programs. Using this model, it is demonstrated that any algorithm for sorting n inputs which is based on comparisons of individual inputs requires time-space product proportional to n2. Uniform and non-uniform sorting algorithms are presented which show that this lower bound is nearly tight.
['Allan Borodin', 'Michael J. Fischer', 'David G. Kirkpatrick', 'Nancy A. Lynch', 'Martin Tompa']
A time-space tradeoff for sorting on non-oblivious machines