list.sort(cmpfunc) question

[Tim Peters]

[Simon Budig]
> ...
> Is the sort-function guaranteed to be stable? Does it keep the order,
> when cmpfunc returns 0 for a pair of items?

No, Python's list.sort() is not stable.  Stability can be "faked", though, by
sorting a derived list y, where each element y[i] == (x[i], i).  Then no two
list elements are equal.  Because tuples are compared lexicographically,
cmp((x, i), (x, j)) has the same sense as cmp(i, j), thus preserving the
original order of equal elements in x.

Caution:  if a list is "short enough", list.sort() falls back to a binary
insertion sort, and IIRC that *is* stable.  So trying out small examples may
fool you.

forewarned-is-forearmed-ly y'rs  - tim