python bisect is O(n^2)?
<p>I'm running a simple test to monitor how long does it take to sort-insert into a list with the <code>bisect</code> library</p>

<pre><code>import numpy as np
import bisect

def get_time(N):
    myl = []
    a = time.time()
    for i in np.arange(N):
        bisect.insort_left(myl, random.randint(0,1000000) )
    b = time.time()
    return (b-a)
</code></pre>

<p>So I call this with:</p>

<pre><code>t_dict = {}
for N in [1000,5000,10000,50000,100000,200000,300000,400000,500000]:
    t_dict[N] = get_time(N)
</code></pre>

<p>and plot the results:</p>

<p><a href="https://i.stack.imgur.com/2oz2x.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/2oz2x.png" alt="enter image description here"></a></p>

<p>I would have guessed/hoped that <code>insort</code> would be at max <code>O(nlog(n))</code>. From the documentation, one reads:</p>

<p>"Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step."</p>

<p>What am I missing here?</p>

<p>EDIT: I was missing something extremely obvious. Anyway, I would like to update the question with the same thing using SortedList from the package SortedContainers:</p>

<p><a href="https://i.stack.imgur.com/YWGBO.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/YWGBO.png" alt="enter image description here"></a></p>

<p>very fast stuff!</p>