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

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.