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

Bertram Felgenhauer bertram.felgenhauer at googlemail.com
Sun Jul 12 03:51:04 EDT 2009


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.html#mergesort


More information about the Haskell-Cafe mailing list