[Haskell-cafe] excercise - a completely lazy sorting algorithm

[Andrew Hunter]

On Mon, Jul 6, 2009 at 4:32 PM, Matthias
Görgens<matthias.goergens at googlemail.com> wrote:
>> It seems to me, that you just need a selection algorithm which works in
>> O(n * k) time for k arbitrary elements. If you combine O(n*k) selection
>> algorithm with any O(n * lg n) sort, you furfil your time constrain.
>
> I guess, we also want the list to be sorted in O(1) after having
> selected every element.
>

I think he's suggesting something along the lines of: for the first
\log n requests, use a selection.  On the \log n + 1th request, just
sort the whole thing.  This obviously isn't the spirit of what's
wanted, but does in fact meet the time bounds.

AHH