Best way to insert sorted in a list

[Ian Kelly]

On Fri, Jun 17, 2011 at 3:02 PM, Shashank Singh
<shashank.sunny.singh at gmail.com> wrote:
> 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.

Finding the position to insert is O(log n), but the actual insert is
O(n).  This is because Python lists are implemented with arrays and
everything after the inserted item has to be moved in memory to make
space for the insert.