Petr Pudlak wrote:
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)?
The (merge) sorting algorithm provided by Data.List has this property, providing the first k elements in O(n + k log(n)) time. (source at [1]) As a mental model, you can think of suspended 'merge' evaluations as internal nodes in a tree, with the two arguments as subtrees. In that model, the algorithm turns into heap sort: It builds a balanced binary tree with n external nodes, taking O(n) time -- this job is done by merge_pairs -- and then repeatedly extracts the minimum element, taking O(log(n)) time for each one. regards, Bertram [1] http://www.haskell.org/ghc/docs/latest/html/libraries/base/src/Data-List.htm...