title: Python: Quicksort with median of three
body: <p>I'm trying to change this quicksort code to work with a pivot that takes a "median of three" instead.</p>
  
  <pre><code>def quickSort(L, ascending = True): 
      quicksorthelp(L, 0, len(L), ascending)
  
  
  def quicksorthelp(L, low, high, ascending = True): 
      result = 0
      if low &lt; high: 
          pivot_location, result = Partition(L, low, high, ascending)  
          result += quicksorthelp(L, low, pivot_location, ascending)  
          result += quicksorthelp(L, pivot_location + 1, high, ascending)
      return result
  
  
  def Partition(L, low, high, ascending = True):
      print('Quicksort, Parameter L:')
      print(L)
      result = 0 
      pivot, pidx = median_of_three(L, low, high)
      L[low], L[pidx] = L[pidx], L[low]
      i = low + 1
      for j in range(low+1, high, 1):
          result += 1
          if (ascending and L[j] &lt; pivot) or (not ascending and L[j] &gt; pivot):
              L[i], L[j] = L[j], L[i]  
              i += 1
      L[low], L[i-1] = L[i-1], L[low] 
      return i - 1, result
  
  liste1 = list([3.14159, 1./127, 2.718, 1.618, -23., 3.14159])
  
  quickSort(liste1, False)  # descending order
  print('sorted:')
  print(liste1)
  </code></pre>
  
  <p>But I'm not really sure how to do that. The median has to be the median of the first, middle and last element of a list. If the list has an even number of elements, middle becomes the last element of the first half.</p>
  
  <p>Here's my median function:</p>
  
  <pre><code>def median_of_three(L, low, high):
      mid = (low+high-1)//2
      a = L[low]
      b = L[mid]
      c = L[high-1]
      if a &lt;= b &lt;= c:
          return b, mid
      if c &lt;= b &lt;= a:
          return b, mid
      if a &lt;= c &lt;= b:
          return c, high-1
      if b &lt;= c &lt;= a:
          return c, high-1
      return a, low
  </code></pre>