On a standard computing model that reflects reality for sequential processing, such as a RAM machine with penalized access time for growing memory, can a comparison sort algorithm work in both logspace yet sub-quadratic time?Standard algorithms for sorting are O(n*log(n)) time yet I've found that once these programs are restricted to only read-only input, write-only output, and pointers for indexing into the I/O, they seem to suddenly require quadratic time.Another question on cstheory prompted answers giving model-independent lower bounds for famous complexity classes such as NP requiring a product of time and space resources to be nearly quadratic. Does that same argument apply here to non-trivial problems in L?
Sorting in sub-quadratic time and logspace simultaneously
complexity theory;sorting
The following paper proves that any comparison-based sorting algorithm must satisfy $TS = \Omega(n^2)$, where $T$ is the running time and $S$ is the amount of read-write space used.Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa.  A Time-Space Tradeoff for Sorting on Non-Oblivious Machines.  Journal of Computer and System Sciences, vol 22 pp.351--364, 1981.In particular, if $S = O(\log n)$, then $T = \Omega(n^2/\log n)$, i.e., if you have only logarithmic space, then the running time has to be nearly quadratic.