12

If I have to sort some list, say a, using the sort method in Python such as below..

a=[3,7,1,0,2,8]
a.sort()
print a

What are the worst, average and best cases of such programs in case of sorting ? And what complexities would they have in each ? What sorting technique does python use in this ?

h8pathak
  • 1,342
  • 3
  • 17
  • 29

1 Answers1

16

Python uses Timsort, which was named after Tim Peters, the Python developer who invented it. The Wikipedia page has complexity information:

Worst case performance  O(nlogn)
Best case performance   O(n)
Average case performance    O(nlogn)
Worst case space complexity O(n)
asmeurer
  • 86,894
  • 26
  • 169
  • 240
  • `Cpython` (and probably other implementations) use Timsort -- The only requirements in the language reference are that the sorting method is stable. I think maybe one or two implementations might use `mergesort` which pretty much the same complexity except for best-case performance. – mgilson Sep 12 '14 at 17:38
  • There’s a [document](http://hg.python.org/cpython/file/default/Objects/listsort.txt) in the source tree that describes how timsort works and performs in detail. – uranusjr Sep 12 '14 at 17:40
  • The C code behind the built-in sort function. http://svn.python.org/view/python/trunk/Objects/listobject.c?revision=69227&view=markup – h8pathak Sep 12 '14 at 17:48
  • It's worth understanding that Timsort's best case is the whole point, because its best cases aren't just some random subset of the space, they include most things that you'd reasonably consider "mostly already sorted". – abarnert Sep 12 '14 at 17:59
  • @asmeurer I have added a part in the question. Please help me with that. – h8pathak Sep 14 '14 at 04:28
  • @h8pathak this question has been closed, so if you have any further questions please open a new question. – asmeurer Sep 14 '14 at 06:45