Python's simplicity philosophy

[Andrew Dalke]

Paul Rubin:
> The change was that native lists will implement stable sort.  My gripe
> is that if native lists are required to sort stably and list-alikes
> can sort unstably, then list.sort and listalike.sort act differently
> in a way that can lead to subtle bugs.
  ...
> > That's a statement only that list.sort shall be stable and
> > not that all .sort() methods must be stable.
>
> It would be icky if some .sort() methods are required to be stable but
> others are not.

I've been thinking about this.  I'm of two minds about it, both
for and against.

The 'for' side, which dominates, says that the only extra work is
for those people who implement a version of Python.  There will
only be few of these, and the work needed to implement at least
a rough cut at a stable sort is pretty minimal.  Any user of a list-alike
sort who is concerned about its stability or wants the code to work
for pre-2.3 will use the DSU idiom.  People who don't know about
differences in how sort algorithms handle ties will have their sorts
work "as expected".

The 'against' side says, as you do, that having list.sort required
to be stable now places an extra barrier to anyone else who
implements a list-alike sort, because that sort should now also
be stable.

What mollifies the latter view is that some user-defined sorts
won't have ties, so there will never be a problem.  And some
user-defined sorts will want a stable sort -- anything which
sorts rows based on a column in a grid display must be stable.
So there are only going to be a relatively few cases where
this will be a problem.

Besides, what I really want is a set of algorithms implemented
independent of the container so that I can have a generic
'sort' function work on a user-defined container.  At that
point it would be trivial for a user-defined list-alike to
implement its .sort() method as a call to the stable-sort
algorithm, which further reduces the number of times when
the expectation of a stable sort causes a problem.

Hmmm.. To do this nicely would seem to require a
'swap' method on lists as otherwise there's a lot of
movements when swapping two items in a list.

> Note that the most obvious way to implement sort() in C is to call the
> standard C library qsort function, which is unstable.

And again I note that I've seen commercial software which
made the expectation that C's qsort(3C) was ... well, not
stable, but it assumed it would give the same results on
different machines.  That error was fixed by implementing
their own sort algorithm.  (It wasn't caught for years because
there are very few ties in their data and even fewer people
moved data from one platform to another.)

My preference is for a stable sort.  It works the right way
for most cases, and no sort algorithm is going to do the
right thing for all cases.  (Hence the explosion of sort
variants you rightly pointed out.)

                    Andrew
                    dalke at dalkescientific.com