Best way to insert sorted in a list

[Shashank Singh]

On Sat, Jun 18, 2011 at 2:23 AM, SherjilOzair <sherjilozair at gmail.com> 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).

Correct me if I am wrong here but isn't the second one is O(log N)?
Binary search?
That is when you have an already sorted list from somewhere and you
are inserting just one new value.
In case you are building the whole list yourself it's the same (N * log N)

>
> Still, the second one works much better, because C code is being used
> instead of pythons.
>
> Still, being a programmer, using the first way (a.insert(x);
> a.sort()), does not feel right.
>
> What has the community to say about this ? What is the best (fastest)
> way to insert sorted in a list ?
> --
> http://mail.python.org/mailman/listinfo/python-list
>



-- 
Regards
Shashank Singh
http://www.cse.iitb.ac.in/~shashanksingh