[Python-Dev] Re: timsort?

[Guido van Rossum]

> [Tim:]
> > > > Note that we switched from doing two minor releases per year, to
> > > > something like one minor release per two years (2.2 was released
> > > > in 2001!).  timsort is less than a year old, IIRC.  Since it can
> > > > raise MemoryError where the 2.2 sort could not, and may compute
> > > > different results on the same inputs, it was much more a new
> > > > feature than a bugfix.
> 
> [me:]
> > > Remind me why raising MemoryError is better than punting
> > > and sorting the list some other way?
> 
> [Guido:]
> > Because the old way requires just as much code as the new way, and we
> > don't want both versions of the code around?
> 
[Gareth]
> Sure, but the old and new ways require all that code only so
> that they can be very fast. Why not switch to a simpler but
> slower sort (say, a simple implementation of quicksort) instead
> of giving a MemoryError?

Yes, why not?

I'm sure with Herculean effort this could be implemented, but given
the rarity of MemoryError, why bother?

Note that *everything* can raise MemoryError so handling this one
special would requires who knows what.

If you have further questions, please pose them in the form of a patch.

--Guido van Rossum (home page: http://www.python.org/~guido/)