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

Thanks. I heard about the hylo-, ana- and catamorphisms before, but never explicitly used them. Time to get started. And yet another question: One can get the median in deterministic linear time. For quicksort choosing the median as pivot keeps the O(n log n) average running time and brings down the expected worst case, too. Do you know of a (natural) way to combine selecting the median and doing the quicksort, so that you don't compare unnecessarily? The way to de-randomize quickselect is to calculate medians of medians. I.e. solve the problem for smaller instances first. I suspect if we follow this strategy with the reified quicksort call-trees, the de-randomized quicksort will look a lot like mergesort.