Best way to insert sorted in a list

[Stephan Houben]

Op 2017-09-08, logonveera at gmail.com schreef <logonveera at gmail.com>:
> On Saturday, June 18, 2011 at 2:23:10 AM UTC+5:30, SherjilOzair wrote:
>> There are basically two ways to go about this.
>> One is, to append the new value, and then sort the list.
>> Another is to traverse the list, and insert the new value at the
>> appropriate position.
>> 
>> The second one's complexity is O(N), while the first one's is O(N *
>> log N).
>> 
>> Still, the second one works much better, because C code is being used
>> instead of pythons.

Python uses the Timsort ( https://en.wikipedia.org/wiki/Timsort )
algorithm. Timsort is O(N) in the special case of a list of N elements
where the first N-1 are already sorted and the last one is arbitrary.

So appending the value and then calling sort() is in fact O(N) in Python
(hence asymptotically optimal), and also practically fast since the
sort() is implemented in C.

Stephan