#!/usr/local/bin/python3
# Author: Dr. Robert Heckendorn, Computer Science Department, University of Idaho, 2013

# begin partition (inserted here so you can see small efficiency mod in partition)
def partition(x) :
    return partitionaux(x, 0, len(x))

# WARNING: does not include value on right so you can use len(x) on right
def partitionaux(x, left, right) :
    pivot = x[left]
    i = left
    j = right
    while (True) :
        i+=1
#        while i<right-1 and x[i]<pivot :    # note the protection for overrun on the right
        while x[i]<pivot :    # protection not needed with median of 3 pivot
            i+=1
        j-=1
        while x[j]>pivot :
            j-=1

        if i>=j : break
        (x[i], x[j]) = (x[j], x[i])
    (x[j], x[left]) = (x[left], x[j])
    return j
# end partition

# sort 2 items in increasing order
def sort2(x, i, j) :
    if x[j]<x[i] : (x[i], x[j]) = (x[j], x[i])

# to a quick sort
def sort(x) :
    sortaux(x, 0, len(x))

# NOTE: sort in array x between left and right-1 inclusive.
def sortaux(x, left, right) :
    print("LEN:", right-left)
    if left<=0 : printl = 0
    else : printl = left-1
    print(x[:printl], "<<", x[left:right], ">>", x[right:])
    if right-left >=3 :
        # make median of 3 the pivot
        midpoint = (left+right)//2
        (x[midpoint], x[left+1]) = (x[left+1], x[midpoint])
        sort2(x, left, left+1)
        sort2(x, left, right-1)
        sort2(x, left+1, right-1)

        # divide up the sorting
        s = partitionaux(x, left+1, right)   # partition based on the median
        sortaux(x, left, s)                  # sort based on the even the smallest of 3
        sortaux(x, s+1, right)
    elif right-left==2 :
        sort2(x, left, right-1)

    return x

y = [99, 1, 31, 41, 59, 26, 53, 58, 97, 93, 23, 84, 62, 64, 33, 83, 27, 9, 50, 28, 8, 41]
sort(y)
print("ans:" , y)