Python sort() method on list vs builtin sorted() function

Question

I know that __builtin__ sorted() function works on any iterable. But can someone explain this huge (10x) performance difference between anylist.sort() vs sorted(anylist) ? Also, please point out if I am doing anything wrong with way this is measured.

"""
Example Output:
$ python list_sort_timeit.py 
Using sort method: 20.0662879944
Using sorted builin method: 259.009809017
"""

import random
import timeit

print 'Using sort method:',
x = min(timeit.Timer("test_list1.sort()","import random;test_list1=random.sample(xrange(1000),1000)").repeat())
print x

print 'Using sorted builin method:',
x =  min(timeit.Timer("sorted(test_list2)","import random;test_list2=random.sample(xrange(1000),1000)").repeat())
print x

---

As the title says, I was interested in comparing list.sort() vs sorted(list). The above snippet showed something interesting that, python's sort function behaves very well for already sorted data. As pointed out by Anurag, in the first case, the sort method is working on already sorted data and while in second sorted it is working on fresh piece to do work again and again.

So I wrote this one to test and yes, they are very close.

"""
Example Output:
$ python list_sort_timeit.py 
Using sort method: 19.0166599751
Using sorted builin method: 23.203567028
"""

import random
import timeit

print 'Using sort method:',
x = min(timeit.Timer("test_list1.sort()","import random;test_list1=random.sample(xrange(1000),1000);test_list1.sort()").repeat())
print x

print 'Using sorted builin method:',
x =  min(timeit.Timer("sorted(test_list2)","import random;test_list2=random.sample(xrange(1000),1000);test_list2.sort()").repeat())
print x

Oh, I see Alex Martelli with a response, as I was typing this one.. ( I shall leave the edit, as it might be useful).

Answer 1

Well, the .sort() method of lists sorts the list in place, while sorted() creates a new list. So if you have a large list, part of your performance difference will be due to copying.

Still, an order of magnitude difference seems larger than I'd expect. Perhaps list.sort() has some special-cased optimization that sorted() can't make use of. For example, since the list class already has an internal Py_Object*[] array of the right size, perhaps it can perform swaps more efficiently.

Edit: Alex and Anurag are right, the order of magnitude difference is due to you accidentally sorting an already-sorted list in your test case. However, as Alex's benchmarks show, list.sort() is about 2% faster than sorted(), which would make sense due to the copying overhead.

Answer 2

Because list.sort does in place sorting, so first time it sorts but next time you are sorting the sorted list.

e.g. try this and you will get same results in timeit case most of the time is spent is copying and sorted also does one more copy

import time
import random
test_list1=random.sample(xrange(1000),1000)
test_list2=random.sample(xrange(1000),1000)

s=time.time()
for i in range(100):
    test_list1.sort()
print time.time()-s

s=time.time()
for i in range(100):
    test_list2=sorted(test_list2)
print time.time()-s

Answer 3

Your error in measurement is as follows: after your first call of test_list1.sort(), that list object IS sorted -- and Python's sort, aka timsort, is wickedly fast on already sorted lists!!! That's the most frequent error in using timeit -- unadvertently getting side effects and not accounting for them.

Here's a good set of measurements, using timeit from the command line as it's best used:

$ python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' '
> y=list(x); y.sort()'
1000 loops, best of 3: 452 usec per loop
$ python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' '
x.sort()'
10000 loops, best of 3: 37.4 usec per loop
$ python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' '
sorted(x)'
1000 loops, best of 3: 462 usec per loop
$

As you see, y.sort() and sorted(x) are neck and neck, but x.sort() thanks to the side effects gains over an order of magnitude's advantage -- just because of your measurement error, though: this tells you nothing about sort vs sorted per se!-)