SELECTION FROM READ-ONLY MEMORY AND SORTING WITH MINIMUM DATA MOVEMENT

Selecting an element of given rank, for example the median, is a funda mental problem in data organization and the computational complexity o f comparison based problems. Here, we consider the scenario in which t he data resides in an array of read-only memory and hence the elements cannot be moved within the array. Under this model, we develop effici ent selection algorithms using very little extra space (o(log n) extra storage cells). These include an O(n(1 divided by epsilon)) worst cas e algorithm and an O(n log log n) average case algorithm, both using a constant number of extra storage cells or indices. Our algorithms com plement the upper bounds for the time-space tradeoffs obtained by Munr o and Paterson [9] and Frederickson [4] who developed algorithms for s election in the same model when Omega((log n)(2)) extra storage cells are available. We apply our selection algorithms to obtain sorting alg orithms that perform the minimum number of data moves on any given arr ay. We also derive upper bounds for time-space tradeoffs for sorting w ith minimum data movement.