title: Dutch national flag sort
body: <p>I'm trying to program a quicksort-ish algorithm using the <a href="http://en.wikipedia.org/wiki/Dutch_national_flag_problem" rel="nofollow">Dutch national flag algorithm</a>. I've tried everything I can to make this work and I'm getting really frustrated. Can you take a look and help me find the bugs?</p>
  
  <pre><code>import random
  
  a = []
  for i in range(100):
      a.append(random.randint(1, 100))
  
  print(a)
  def partion(array, left, right, lPiv, rPiv):
          high = len(array) -1
          p = left
          i = left
          while i &lt; high:
                  if array[i] &lt; lPiv and array[i] &lt; rPiv:
                          array[i],array[p]=array[p],array[i]
                          p = p+1
                          i = i+1
                  elif array[i] &gt; lPiv and array[i] &gt; rPiv:
                          array[i],array[high]=array[high],array[i]
                          high = high-1
                  else:
                          i = i+1
  
          return [p, high]
  
  def piv(array, left, right):
      aMin = array[left]
      aMax = array[left]
  
      for i in array:
        if i &lt; aMin:
            aMin = i
        if i &gt; aMax:
            aMax = i
      return [aMin + ((aMax - aMin) /3), aMin + ((aMax-aMin)/3)*2]
  
  
  def sort(array, left, right, depth):
      apiv = piv(array, left, right)
      part = partion(array, left, right, apiv[0], apiv[1])
      if right-left &gt;= 3:
          piv1 = piv(array, left, part[0])
          part1 = partion(array, left, part[0], piv1[0], piv1[1])
          sort(array, left, part1[0], depth+1)
  
  
          piv2 = piv(array, part[0], part[1])
          part2 = partion(array, part[0], part[1], piv2[0], piv2[1])
          sort(array, part[0], part[1])
  
          piv3 = piv(array, part[1], right)
          part3 = partion(array, part[1], right, piv3[0], piv3[1] )
          sort(array, part[1], right)
  
      elif right-left &lt; 3:
          if array[right] &lt; array[left]:
              array[right],array[left] = array[left], array[right]
          else:
              return
  
  
  sort(a, 0, len(a), 1)
  print(a)
  </code></pre>