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 ?

Improve this question
3
  • 1
    Also see About python's built in sort() method and Python internal sort method Commented Sep 12, 2014 at 17:38
  • This question is more specific. Commented Sep 12, 2014 at 17:50
  • Not really; the method and complexity are named in the specific duplicate, and you can get more info still from the links provided. Commented Sep 12, 2014 at 18:18

1 Answer 1

Reset to default
17

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)
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

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.
There’s a document in the source tree that describes how timsort works and performs in detail.
The C code behind the built-in sort function. svn.python.org/view/python/trunk/Objects/…
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".
@asmeurer I have added a part in the question. Please help me with that.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.