Heinrich Apfelmus wrote:
Why should it be uniform just because it looks nice? Looks can be deceiving, you need a mathematical proof to be certain.
My claim was that it is "uniform and simple"; naturally neither follows from the other, but each has merit.
Embarrassingly, the analysis in my previous message is wrong, though. Here an actually correct assessment of the algorithm. Or rather, of the two algorithms; the results are different depending on whether you use a pivot *element* or just a pivot *position*. It will turn out that the former is not uniform, while, to my surprise, the latter is uniform!
And this was my point. I never considered a pivot *element*, which you correctly point out wouldn't work so well. I was referring to a pivot taken from a randomly chosen *position*. On re-reading Gabriel Scherer's original musing:
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 ?
I may have misunderstood his original intent, as he refers to a random "result position" for a pivot (chosen how?). But if that's changed to choosing the pivot from a random position, then it works out nicely. I think you agree with this later in your email. And finally, re-reading your earlier comment:
First, you can skip choosing the pivot position because it is already entailed by the choices of elements left and right to it.
I think I understand now what you were referring to... (redundantly) choosing the destination for a pivot chosen by some other unspecified means. It seems we were talking beside each other; I'm sorry if I misunderstood you earlier. Cheers, John Dorsey