ppbs_descr_code

// here: pseudo-code
init(Array A, Pivot p)
  m1 = 0
  foreach(elem in A): if elem < p then m1++
  m2 = m1
  foreach(elem in A): if elem == p then m2++
  i1 = 0
  i2 = m1
  i3 = m2
  while(i1 < m1 and A[i1] < p) i1++
  while(i2 < m2 and A[i1] == p) i2++
  while(i3 < A.length and A[i3] > p) i3++


partition(Array A, Pivot p)
  until(i1 == m1 and i2 == m2 and i3 == A.length) do:
      if i1 < m1
          if A[i1] == p
              swap A[i1] with A[i2]
              while(i2 < m2 and A[i2] == p) i2++
          else
              swap A[i1] with A[i3]
              while(i3 < A.length and A[i3] > p) i3++
          while(i1 < m1 and A[i1] < p) i1++
      else
          swap A[i2] with A[i3]
          while(i2 < m2 and A[i2] == p) i2++
          while(i3 < A.length and A[i3] > p) i3++
  return m1 and m2