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

[Matthias Görgens]

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.