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

Petr Pudlak deb at pudlak.name
Mon Jul 6 15:26:38 EDT 2009

Hi all,

immediately we asked: Would it be possible to create a lazy selection/sorting
algorithm so that getting any element of the sorted list/array by its index
would require just O(n) time, and getting all the elements would still be in
O(n * log n)?

array). Asking k arbitrary elements should take no more than

I believe that this could be done, but so far I wasn't able to implement and
show it myself. I think the solution would be somewhat modified lazy quicksort
(or "Median of Medians algorithm" if we want to be sure that we get good

Perhaps somebody else would also like to give it a try? Or perhaps explain me
why it's not possible?

    Best regards,

More information about the Haskell-Cafe mailing list