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

[Petr Pudlak]

Hi all,

about a month ago, we were discussing sorting in Haskell with a friend. We
realized a nice property of lazy merge-sort (which is AFAIK the implementation
of Data.List.sort): Getting the first element of the sorted list actually
requires O(n) time, not O(n * log n) as in imperative languages. And
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)?

More precisely: The result of sorting an n-element list or array should be a
structure that allows to ask i-th element of the result (for example, a lazy
array). Asking k arbitrary elements should take no more than
  O(min(n * log n, k * n))

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

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

    Best regards,
    Petr