three_way_partitioning.py

def three_way(a, lo, hi):
  ''' dutch national flag problem for 3-way partitioning in quicksort'''
  
  key = a[random.randint(lo, hi)]
  less, equal = lo
  greater = hi
  while equal < high:
    if a[less] < key:
      a[less], a[equal] = a[equal], a[less]
      less += 1
      equal += 1
    elif a[less] == key:
      equal += 1
    else:
      greater -= 1
      a[greater], a[equal] = a[equal], a[greater]