List appears to be empty during sorting

Question

I wanted to sort a list in-place and tried using the list itself during the sorting (within a key function). I found out that the list itself appears to be empty in there.

a = [1,4,5,3,2,6,0]
b = ['b', 'e', 'f', 'd', 'c', 'g', 'a']
b.sort(key=lambda x: a[b.index(x)])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in <lambda>
ValueError: 'b' is not in list

So I tried:

def f(x):
  print "FOO:", x, b
  return b.index(x)

b.sort(key=f)

and got

FOO: b []
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in f
ValueError: 'b' is not in list

Any explanation for this?

Answer 1

From the listobject.c source code:

/* The list is temporarily made empty, so that mutations performed
 * by comparison functions can't affect the slice of memory we're
 * sorting (allowing mutations during sorting is a core-dump
 * factory, since ob_item may change).
 */

and from the Mutable Sequence Types documentation:

CPython implementation detail: While a list is being sorted, the effect of attempting to mutate, or even inspect, the list is undefined. The C implementation of Python 2.3 and newer makes the list appear empty for the duration, and raises ValueError if it can detect that the list has been mutated during a sort.

You could zip a and b instead:

b[:] = [bval for (aval, bval) in sorted(zip(a, b))]