[Python-Dev] Sorting

[Tim Peters]

[Aahz]
> ...
> It seems pretty clear by now that the new mergesort is going to replace
> samplesort, but since nobody else has said this, I figured I'd add one
> more comment:
>
> I actually understood your description of the new mergesort algorithm.
> Unless you can come up with similar docs for samplesort, the Beer Truck
> scenario dictates that mergesort be the new gold standard.
>
> Or to quote Tim Peters, "Complex is better than complicated."

Good observation!  I wish I'd thought of that <wink>.  The mergesort is more
complex, but it doesn't have so many fiddly little complications obscuring
it.  There were was an extensive description of the samplesort hybrid in
listobject.c's comments, but you know you're in Complication Heaven when
you've got to document half a dozen distinct "tuning macros" in hand-wavy
terms.  The only tuning parameter in the meregesort is MIN_GALLOP, and the
tradeoff it makes is explainable.