title: Inplace insertion sort slower than insertion sort that creates a new list?
body: <pre><code>def insertion(sequence):
      for i in range(1, len(sequence)):
          key = sequence[i]
          j = search(sequence,0,i-1,key)
          while i &gt; j:
              sequence[i], sequence[i-1] = sequence[i-1], sequence[i]
              i = i - 1
      return sequence
  
  def insertion2(sequence):
      new_li = [sequence[0]]
      for i in range(1,len(sequence)):
          key = sequence[i]
          j = search(new_li,0,len(new_li)-1,key)
          new_li.insert(j,key)
      return new_li
  </code></pre>
  
  <p>I have 2 insertions with 2 approaches. insertion is taking significantly longer than insertion2 (5.346 as compared to 0.0313). Need help figuring out why</p>
  
  <p>PS: The search is basically an auxiliary function for binary search.</p>