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

Andrew Hunter andrewhhunter at gmail.com
Mon Jul 6 19:42:33 EDT 2009


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


More information about the Haskell-Cafe mailing list