title: Why is this python code taking so long?
body: <p>Alright, I have this python code that compares merge sort and selection sort, but it is taking forever.  When done from n = 0 to 90,000 (the size of the list), it only takes about 3 seconds to sort the list.  By this logic, it would take about 10 * 3 * 9 seconds (number of run throughs * duration * incremented run throughs [ we start with 10,000 then do 20,000, then 30,000, etc ] ).  However, it takes far longer than that.</p>
  
  <pre><code>import time
  import random
  
  # Selection Sort Code #
  def maxIndex(J):
      return J.index(max(J))
  
  def swap(LCopy, i, j):
      temp = LCopy[i]
      LCopy[i] = LCopy[j]
      LCopy[j] = temp
  
  # Implementation of selection sort
  def selectionSort(L):
      for i in range(len(L)-1, 1, -1):
          j = maxIndex(L[0:i+1])
          swap(L, i, j)
  
  # Merge Sort Code #
  # Assumes that L[first:mid+1] is sorted and also
  # that L[mid: last+1] is sorted. Returns L with L[first: last+1] sorted
  
  def merge(L, first, mid, last):
  
      i = first # index into the first half
      j = mid + 1 # index into the second half
  
      tempList = []
  
      # This loops goes on as long as BOTH i and j stay within their
      # respective sorted blocks
      while (i &lt;= mid) and (j &lt;= last):
          if L[i] &lt;= L[j]:
              tempList.append(L[i])
              #print L[i], "from the first block"
              i += 1
          else:
              tempList.append(L[j])
              #print L[j], "from the second block"
              j += 1
  
      # If i goes beyond the first block, there may be some elements
      # in the second block that need to be copied into tempList.
      # Similarly, if j goes beyond the second block, there may be some
      # elements in the first block that need to be copied into tempList
      if i == mid + 1:
          tempList.extend(L[j:last+1])
          #print L[j:last+1], "some elements in second block are left over"
      elif j == last+1:
          tempList.extend(L[i:mid+1])
          #print L[i:mid+1], "some elements from first block are left over"
  
      L[first:last+1] = tempList
      #print tempList
  
  
  # The merge sort function; sorts the sublist L[first:last+1]    
  def generalMergeSort(L, first, last):
      # Base case: if first == last then it is already sorted
  
      # Recursive case: L[first:last+1] has size 2 or more
      if first &lt; last:
          # divide step
          mid = (first + last)/2
  
          # conquer step
          generalMergeSort(L, first, mid)
          generalMergeSort(L, mid+1, last)
  
          # combine step
          merge(L, first, mid, last)
  
  # Wrapper function
  def mergeSort(L):
      generalMergeSort(L, 0, len(L)-1)
  
  
  
  m = 10
  n = 100000
  n_increments = 9
  baseList = [ random.randint(0,100) for r in range(n) ]
  
  
  i = 0
  
  while i &lt; n_increments:
      j = 0
      sel_time = 0
      mer_time = 0
  
      while j &lt; m:
          # Do a Selection Sort #
          x = time.clock()
  
          selectionSort( baseList)
  
          y = time.clock()
  
          sel_time += ( y - x )
  
          random.shuffle( baseList )
  
          # Do a Merge Sort #
  
          x = time.clock()
  
          mergeSort( baseList )
  
          y = time.clock()
  
          mer_time += ( y - x )
  
          random.shuffle( baseList )
  
          j += 1
      print "average select sort time for a list of", n, "size:", sel_time / m
      print "average merge sort time for a list of", n, "size:", mer_time / m
  
      j = 0
      i += 1
      n += 10000
  </code></pre>