A TIME-SPACE TRADEOFF FOR SORTING ON NON-OBLIVIOUS MACHINES*

A model of computation is introduced which permits the analysis of both the time and space require-ments of non-oblivious programs. Using this model, it is demonstrated that any algorithm for sorting n inputs which is based on comparisons of indivi-dual inputs requires time-space product propor-tional to n2. Uniform and non-uniform sorting algorithms are presented which show that this lower bound is nearly tight. 1. Hotivation and Contraposition to Previous Research The traditional approach to studying the complexi-ty of a problem has been to examine the amount of some single resource (usually time or space) re-quired to perform the computation. In an effort to better understand the complexity of certain problems, recent attention has been focused on examining the trade off between the required time and space. This paper adopts the latter strategy in order to pursue the complexity of sorting. The vast majority of time-space tradeoffs recently demonstrated have been for "straight-line " (or "oblivious") programs 1, 5, 7, 10, 11,13, 14, 15, that is, programs in which the sequence of opera-tions is independent of the actual values of the inputs. In this model, "time " refers to the num-ber of operations performed, and "space " to the number of auxiliary (i.e., non-input and non-output) registers used to store intermediate results. (To distinguish this usage of space from others which follow, this will be referred to as "data space".) The problem of sorting has been considered in this rontext by Tompa 15, who demonstrated that any oblivious algorithm which sorts n inputs requires time-space product ~(n2). Although oblivious sorting algorithms have been studied extensively (see Knuth 6, where they are called "sorting networks"), most sorting algo-rithms are non-oblivious; that is, they continual-ly test and branch based on comparisons of inpu