title: Why is this merge sort code a lot slower than python's default sort()?
body: <p>I took this merge sort example from a blog. I'm just starting to study merge sort and I wanted to check its speed compared to python's default sorting algorithm. With short random generated lists it's not very noticeable but with a big list, like one with 1,000,000 integers, it takes around 10 seconds, while python's default sorting algorithm doesn't even comes close to 1 second.</p>
  
  <pre><code>import random
  import time
  
  
  def mergeSort(alist):
  
   if len(alist)&gt;1:
     mid = len(alist)//2
     lefthalf = alist[:mid]
     righthalf = alist[mid:]
  
     mergeSort(lefthalf)
     mergeSort(righthalf)
  
     i=0
     j=0
     k=0
  
     while i &lt; len(lefthalf) and j &lt; len(righthalf):
         if lefthalf[i] &lt; righthalf[j]:
             alist[k]=lefthalf[i]
             i=i+1
         else:
             alist[k]=righthalf[j]
             j=j+1
         k=k+1
  
     while i &lt; len(lefthalf):
         alist[k]=lefthalf[i]
         i=i+1
         k=k+1
  
     while j &lt; len(righthalf):
         alist[k]=righthalf[j]
         j=j+1
         k=k+1
  
  
  array = [random.randint(0,1000) for a in range(0,10000)]
  
  #print "original random generated array:",array
  
  start = time.clock()
  
  sorted_array = mergeSort(array)
  
  #print "\nSorted array: ", sorted_array
  
  print "Time: ", str(time.clock() - start)
  
  start1 = time.clock()
  
  array = array.sort()
  
  print "Time: ", str(time.clock() - start1)
  </code></pre>