quick3way.py

import random

def sort(arr):
    random.shuffle(arr)    
    _sort(arr, 0, len(arr) - 1)

def _sort(arr, lo, hi):
    if hi <= lo: return
    lt = lo
    gt = hi
    pivot = arr[lo]
    i = lo
    while i <= gt:
        if arr[i] < pivot:
            _exch(arr, i, lt)
            i += 1
            lt += 1
        elif arr[i] > pivot:
            _exch(arr, i, gt)
            gt -= 1
        else:
            i += 1
    # a[lo:lt] < v == a[lt:gt+1] < a[gt+1:hi+1]
    _sort(arr, lo, lt-1)
    _sort(arr, gt+1, hi)

def _exch(arr, i, j):
    k = arr[i]
    arr[i] = arr[j]
    arr[j] = k