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

[Matthias Görgens]

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.