[Haskell-beginners] Re: randomize the order of a list

[John Dorsey]

Gabriel Scherer wrote:

>> Thanks for the link apfelmus, it's fairly interesting. The key to
>> making it work is the weighting of lists during merging based on their
>> lengths. I wonder if other sort algorithm can be adapted in such a
>> way, while preserving uniformity. Quicksort for example : is it enough
>> to choose the result position of the pivot randomly, and then placing
>> elements on either side with a probability of 1/2 ?

to which Heinrich Apfelmus answered:

> Interesting question! Adapting quick sort is not that easy, though.
>
> First, you can skip choosing the pivot position because it is already  
> entailed by the choices of elements left and right to it.

I don't think this is true...

> Second, probability 1/2 won't work, it doesn't give a uniform  
> distribution.

... because of this.

In fact, it appears to me that the proposed modification to quicksort is
uniform and simple.  Why do you think otherwise?

Cheers,
John