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?