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

Matthias Görgens matthias.goergens at googlemail.com
Mon Jul 6 19:32:13 EDT 2009

> 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.


More information about the Haskell-Cafe mailing list