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