Why is Python's "sorted()" slower than "copy, then .sort()"

Question

Here is the code I ran:

import timeit

print timeit.Timer('''a = sorted(x)''', '''x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]''').timeit(number = 1000)
print timeit.Timer('''a=x[:];a.sort()''', '''x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]''').timeit(number = 1000)

and here are the results:

0.00259663215837
0.00207390190177

I would like to know why using .sort() is consistently faster than sorted() even though both are copying lists?

Note: I am running Python 2.7 on an 2.53Ghz i5 with Win7

Answer 1

The difference you are looking at is miniscule, and completely goes away for longer lists. Simply adding * 1000 to the definition of x gives the following results on my machine:

2.74775004387
2.7489669323

My best guess for the reason that sorted() was slightly slower for you is that sorted() needs to use some generic code that can copy any iterable to a list, while copying the list directly can make the assumption that the source is also a list. The sorting code used by CPython is actually the same for list.sort() and sorted(), so that's not what is causing the difference.

Edit: The source code of the current development version of sorted() does the moral equivalent of

a = list(x)
a.sort()

and indeed, using this code instead of your second version eliminates any significant speed differences for any list sizes.

Answer 2

In support of @Sven Marnach's answer:

There is a small difference for small lists:

$ python2.7 -mtimeit -s "x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]; s=sorted" "a=s(x)"
1000000 loops, best of 3: 1.87 usec per loop

$ python2.7 -mtimeit -s "x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]" "a=x[:];a.sort()"
1000000 loops, best of 3: 1.66 usec per loop

The difference goes away with * 1000 (larger lists):

$ python2.7 -mtimeit -s "x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]*1000; s=sorted" "a=s(x)"
100 loops, best of 3: 3.42 msec per loop

$ python2.7 -mtimeit -s "x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]*1000" "a=x[:];a.sort()"
100 loops, best of 3: 3.48 msec per loop