What is the sort(already_sorted_list) complexity in Python? Does Python check if given iterable is sorted, or do I have to do it by myself? I could not find it anywhere in the docs.
10
votes
Now I need to look up the full implementation of the Tim-Sort algorithm. The answer though is yes, it does some look-ahead comparison to determine if something is already sorted, or almost sorted.
- g.d.d.c
en.wikipedia.org/wiki/Timsort
- Martijn Pieters♦
There is a great wiki entry that discusses the time complexity of many Python functions.
- Burhan Khalid
2 Answers
14
votes
This is entirely implementation dependent. All that python guarantees is that the builtin sorting algorithm is stable (elements which compare equal retain their relative ordering). An implementation could even use a stable bubble sort if it wanted to ...
Cpython uses TimSort (a hybrid of insertion sort an mergesort) which I believe has O(N) complexity if the input is already sorted -- It picks up the best case performance of insertion sort and the worst case performance of mergesort (O(NlogN)).
And if you're curious about the implementation, the source code has a very nice description.
1
votes
Python's sort is called timsort. Its average case performance is O(nlog(n)). It performs really well with pre-sorted lists because it's implementation is designed to seek out runs of sorted elements in the list.
