Is there a general algorithm to implement SQL’s ORDER BY with OFFSET/LIMIT more efficiently than sorting all the records?

The algorithm for a simple TOP x is easy enough. It takes one full pass through the data, but only x records ever need to be sorted. The amortised complexity is O(n), for a set of n rows, assuming x is much less than n.

SO the naive approach to OFFSET y LIMIT z would be to treat it as TOP (y+z) and then return only the z rows. This would be O(n) if y+z is small, and something like O(nlog(n/2)) if y+z is half of n. [Larger values are handled by reversing the sense of the ordering.]

I see that a variant of selection sort can find the median value in O(n), but I haven’t been able to pin down an algorithm for this particular problem.