title: Why is my MergeSort so slow in Python?
body: <p>I'm having some troubles understanding this behaviour.
  I'm measuring the execution time with the timeit-module and get the following results for <strong>10000</strong> cycles:</p>
  
  <ul>
  <li>Merge : <strong>1.22722930395</strong></li>
  <li>Bubble: 0.810706578175</li>
  <li>Select: 0.469924766812</li>
  </ul>
  
  <p><strong>This is my code for MergeSort:</strong></p>
  
  <pre><code>def mergeSort(array):
      if len(array) &lt;= 1:
          return array
      else:
          left = array[:len(array)/2]
          right = array[len(array)/2:]
          return merge(mergeSort(left),mergeSort(right))
  
  def merge(array1,array2):
      merged_array=[]
      while len(array1) &gt; 0 or len(array2) &gt; 0:
  
          if array2 and not array1:
              merged_array.append(array2.pop(0))
  
          elif (array1 and not array2) or array1[0] &lt; array2[0]:
              merged_array.append(array1.pop(0))
  
          else:
              merged_array.append(array2.pop(0))
      return merged_array
  </code></pre>
  
  <h2><strong>Edit:</strong></h2>
  
  <p>I've changed the list operations to use pointers and my tests now work with a list of 1000 random numbers from 0-1000. (btw: I changed to only 10 cycles here)</p>
  
  <p><strong>result:</strong></p>
  
  <ul>
  <li>Merge : <strong>0.0574434420723</strong></li>
  <li>Bubble: 1.74780097558</li>
  <li>Select: 0.362952293025</li>
  </ul>
  
  <p><strong>This is my rewritten merge definition:</strong></p>
  
  <pre><code>def merge(array1, array2):
      merged_array = []
      pointer1, pointer2 = 0, 0
      while pointer1 &lt; len(array1) and pointer2 &lt; len(array2):
          if array1[pointer1] &lt; array2[pointer2]:
              merged_array.append(array1[pointer1])
              pointer1 += 1
          else:
              merged_array.append(array2[pointer2])
              pointer2 += 1
      while pointer1 &lt; len(array1):
          merged_array.append(array1[pointer1])
          pointer1 += 1
  
      while pointer2 &lt; len(array2):
          merged_array.append(array2[pointer2])
          pointer2 += 1
  
      return merged_array
  </code></pre>
  
  <p>seems to work pretty well now :)</p>