title: QuickSort - Median Three
body: <p>I am working on the QuickSort - Median Three Algorithm.
  I have no problem with the first and last element sorting. But, when comes to the Median-three, I am slightly confused. I hope someone could help me on this.</p>
  
  <p>Would be appreciate if someone could provide me some pseudocode?</p>
  
  <p>My understanding is to get the middle index by doing this. (start + end) / 2 , then swap the middle pivot value to the first value, after all these done it should goes well with the normal quick sort ( partitioning and sorting).</p>
  
  <p>Somehow, I couldn't get it works. Please help!</p>
  
  <pre><code>#Array Swap function
  def swap(A,i,k):
      temp=A[i]
      A[i]=A[k]
      A[k]=temp
  
  # Get Middle pivot function    
  def middle(lista):
      if len(lista) % 2 == 0:
          result=  len(lista) // 2 - 1
      else:
          result =  len(lista)  // 2
      return result
  
  def median(lista):
      if len(lista) % 2 == 0:
          return sorted(lista)[len(lista) // 2 - 1]
      else:
          return sorted(lista)[len(lista) // 2]
  
  
  # Create partition function
  def partition(A,start,end):
  
      m = middle(A[start:end+1])
      medianThree = [ A[start], A[m], A[end] ]
  
      if A[start] == median(medianThree):
  
         pivot_pos = start
  
      elif A[m] == median(medianThree):
         tempList = A[start:end+1]
         pivot_pos = middle(A[start:end+1])
         swap(A,start,pivot_pos+start)
  
      elif A[end] == median(medianThree):
  
         pivot_pos = end
  
  
  
      #pivot = A[pivot_pos]
      pivot = pivot_pos
      # swap(A,start,end) // This line of code is to switch the first and last element pivot
      swap(A,pivot,end)
      p = A[pivot]
      i = pivot + 1
      for j in range(pivot+1,end+1):
          if A[j] &lt; p:
              swap(A,i,j)
              i+=1
      swap(A,start,i-1)
      return i-1
  
  
  count = 0
  #Quick sort algorithm
  def quickSort(A,start,end):
      global tot_comparisons
  
      if start &lt; end:
         # This to create the partition based on the 
         pivot_pos = partition(A,start,end)
         tot_comparisons += len(A[start:pivot_pos-1]) + len(A[pivot_pos+1:end])
         # This to sort the the left partition
         quickSort(A,start,pivot_pos -1)
         #This to sort the right partition
         quickSort(A,pivot_pos+1,end)
  </code></pre>