Sorting using lambda not working in Py2.1?

[Tim Peters]

[Tim Peters]
> In a similar vein, the current sort happens to be stable for
> small lists, but isn't stable in general.

[Brian Kelley]
> What do you mean by stable in this case?

It's std terminology in the sort biz:  a sort is "stable" if it preserves
the relative order of records with equal keys.  For example, picture a GUI
email client with columns of info, like Subject and Date, where you can sort
a column by clicking on its header.  Suppose you click on Date first, and
later click on Subject.  If the sort is stable, then within items having the
same Subject, the Date order will be preserved.  Else the Dates within a
given Subject may come in any order at all.

This is less interesting in Python than in many other languages, because
tuple comparison in Python is automagically lexicographic, so that you can
*conveniently* sort records on, e.g., (Subject, Date) tuples, using Subject
as the primary key and Date as a secondary ("tie-breaker") key.  In languages
where that's clumsy, there's more pressure for stable sorts so that the same
effect can be gotten via chaining together multiple sorts.

Here's an exercise that will let you reverse engineer the value of
listobject.c's MINSIZE #define <wink>:

from __future__ import nested_scopes

def build_case(n):
    from random import randrange
    return [(randrange(10000), randrange(10000)) for i in xrange(n)]

def sort_twice(x):
    for i in 1, 0:
        x.sort(lambda a, b: cmp(a[i], b[i]))
    return x

def test(x):
    once = x[:]
    once.sort()
    twice = sort_twice(x)
    if once != twice:
        print "Oops!  They're different:", once, twice

def try_one(n):
    test(build_case(n))

Run try_one(n) with various values of n.  test(n) builds a test list of n
random 2-tuples, sorts it once directly and another time twice (first on the
2nd tuple elements, then on the 1st).  If the sort wasn't stable, it's very
likely to print "Oops!", else it prints nothing.

Now for some values of n you can try this all year and never see an "Oops!".
There's a particular value of n at which it first becomes *possible* to see
"Oops!", and the larger n the more likely that becomes.

The cutoff point is the size where list.sort() switches from using a (stable)
binary insertion sort to a (unstable) samplesort/insertion hybrid.

there's-little-truth-to-the-rumor-that-whether-a-sort-is-
    stable-reflects-its-author's-personality-ly y'rs  - tim