A time-space tradeoff for sorting on non-oblivious machines
Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy Ann Lynch, Martin Tompa · 1979
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.