Python sorted() key function weirdness

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开发者_StackOverflow中文版 fine (compatibility is the reason why I am not using it)?

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.

the last one is imho simply wrong! It should be: [1, 2, 0]

In your second example, the key is lambda a: aa[a] which gives you the indices of the elements in increasing size order.

In the last example, the key is lambda a: -aa[a]. Due to the negation, this gives you the indices of the elements in decreasing size order.

So the last result should be [2, 0, 1] - it's the reverse of [1, 0, 2].

In this example

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

you're getting the indices of the elements in increasing size order - [2, 0, 1] corresponds to [-20, -10, -5].

In your last two examples, you're again getting the indices for the elements in increasing size order ([2, 0, 1]), or decreasing size order ([1, 0, 2]).

This makes sense to me

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