#!/usr/local/bin/python3
# Author: Dr. Robert Heckendorn, Computer Science Department, University of Idaho, 2013
from partition2 import *
# this quicksort uses coarse graining and insertion sort

def sortinsert(x) :
    for i in range(1, len(x)) :
        # everything before position i is sorted.
        # insert x[i] somewhere before position i.
        minv = x[i]
        j = i-1
        while j>=0 and x[j]>minv :
            x[j+1] = x[j]
            j -= 1
        x[j+1] = minv
    return x

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

# quicksort at coarse granularity and insert sort to finish it off
def sort(x) :
    sortaux(x, 0, len(x))
    sortinsert(x)

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 >=8 :                  # here 8 is the level of granularity
        # 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)

    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, 39, 9, 37, 5, 10, 58, 20, 9, 74, 94, 4]
sort(y)
print("ans:" , y)