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

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

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 = [31, 41, 59, 26, 53, 58, 97, 93, 23, 84, 62, 64, 33, 83, 27, 9, 50, 28, 8, 41, 97, 1, 69, 3, 99, 37, 5, 10]
sort(y)
print("ans:" , y)