Python sorted() key function weirdness

Question

While I was debugging some illogical behavour I came to the following weirdness in Python 2.5 sorted() function calls:

>>> aa = [10, 5, 20]
>>> sorted(range(len(aa)))
[0, 1, 2]
sorted(range(len(aa)), key=lambda a: aa[a])
[1, 0, 2]
sorted(range(len(aa)), key=lambda a: -aa[a])
[2, 0, 1]

First two calls work as expected, but the last one is imho simply wrong! It should be: [1, 2, 0].

After further experiments for trying to come to the root of the problem I came to this (does not use lambda or negation operation, but it is otherwise the same problem):

>>> bb = [-10, -5, -20]
>>> sorted([0, 1, 2], key=bb.__getitem__)
[2, 0, 1]

Even things like following don't work and show that double negation works again:

>>> bb = [-10, -5, -20]
>>> def fun(i):
...    return bb[i]
>>> sorted([0, 1, 2], key=fun)
[2, 0, 1]
>>> def fun2(i):
...     return -bb[i]
>>> sorted([0, 1, 2], key=fun2)
[1, 0, 2]

Am I losing my mind or where is the problem? Or why doesn't Python 3.x have the cmp argument that used to work fine (compatibility is the reason why I am not using it)?

Answer 1

The value returned by the key function acts as a proxy for the values being sorted. So when you say

sorted(range(len(aa)), key=lambda a: -aa[a])

you are sorting range(len(aa)), that is [0, 1, 2], but using the values -aa[0], -aa[1], -aa[2] as the proxy values.

range(len(aa))   0   1   2    <-- values
aa[a]           10   5  20
-aa[a]         -10  -5 -20    <-- proxy values

Since -20, or -aa[2], is the smallest proxy value, its associated value 2 becomes the first element in the sorted result.

Since -10, or -aa[0] is the next smallest, its associated value 0 becomes the second element in the sorted result.

Finally -5, or -aa[1] is the last value, so 1 is the last number in the sorted result.

Thus, sorted(range(len(aa)), key=lambda a: -aa[a]) equals [2, 0, 1].

The answer Python is giving is correct.