[Haskell-cafe] excercise - a completely lazy sorting algorithm
matthias.goergens at googlemail.com
Mon Jul 6 16:17:10 EDT 2009
Interesting problem. I have been toying with the same problem for some time.
To solve the problem in theory, I'd concentrate on getting the number
of comparisons into the required O(n) resp. O(n log n) ranges.
Afterwards we can think about building the infrastructure to keep the
number of all operations (book keeping..) in those bounds, too.
Anyway, I'll give a solution to the problem using a randomized
quicksort, soon. Later we can replace the randomized pivote-picking
with a deteministic linear-median algorithm.
More information about the Haskell-Cafe