<div class="gmail_quote">On Wed, Feb 8, 2012 at 4:25 PM, Guido van Rossum <span dir="ltr"><<a href="mailto:guido@python.org" target="_blank">guido@python.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

Also note that "many times" is actually O(log N) per insertion, which isn't so bad. The main use case for bisect() is to manage a list that sees updates *and*  iterations -- otherwise building the list unsorted and sorting it at the end would make more sense. The key= option provides a balance between the cost/elegance for updates and for iterations.<br>

</blockquote><div><br></div><div>Maintaining a sorted list using Python's list type is a trap.  The bisect is O(log n), but insertion and deletion are still O(n).</div><div><br></div><div>A SortedList class that provides O(log n) insertions is useful from time to time.  There are several existing implementations available (I wrote one of them, on top of my blist type), each with their pros and cons.</div>

</div><div><br></div>-- <br>Daniel Stutzbach<br>