Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #7860

Re: Best way to insert sorted in a list

References <c63e771c-8968-4d7a-9c69-b7fa6ff34e09@35g2000prp.googlegroups.com> <BANLkTin-76BecXqwnHCaegYQyQ24gsp9BQ@mail.gmail.com>
From Ian Kelly <ian.g.kelly@gmail.com>
Date 2011-06-17 15:23 -0600
Subject Re: Best way to insert sorted in a list
Newsgroups comp.lang.python
Message-ID <mailman.93.1308345873.1164.python-list@python.org> (permalink)

Show all headers | View raw

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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Best way to insert sorted in a list SherjilOzair <sherjilozair@gmail.com> - 2011-06-17 13:53 -0700
  Re: Best way to insert sorted in a list Shashank Singh <shashank.sunny.singh@gmail.com> - 2011-06-18 02:32 +0530
  Re: Best way to insert sorted in a list Ethan Furman <ethan@stoneleaf.us> - 2011-06-17 14:31 -0700
  Re: Best way to insert sorted in a list Ian Kelly <ian.g.kelly@gmail.com> - 2011-06-17 15:23 -0600
  Re: Best way to insert sorted in a list Chris Torek <nospam@torek.net> - 2011-06-17 21:48 +0000
    Re: Best way to insert sorted in a list Ethan Furman <ethan@stoneleaf.us> - 2011-06-17 15:24 -0700
    Re: Best way to insert sorted in a list Ian Kelly <ian.g.kelly@gmail.com> - 2011-06-17 17:33 -0600
      Re: Best way to insert sorted in a list Chris Torek <nospam@torek.net> - 2011-06-18 00:46 +0000
  Re: Best way to insert sorted in a list Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-06-18 02:27 +0000
  Re: Best way to insert sorted in a list Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2011-06-17 21:21 -0700
  Re: Best way to insert sorted in a list Vito De Tullio <vito.detullio@gmail.com> - 2011-06-19 16:21 +0200

csiph-web