from time import clock
import sys
def HeapSort(A):
    global cmp
    def heapify(A):
        global cmp
        start = (len(A) - 2) / 2
        while start >= 0:
            cmp=cmp+1
            shiftDown(A, start, len(A) - 1)
            start -= 1

    def shiftDown(A, start, end):
        global cmp
        root = start
        while root * 2 + 1 <= end:
            cmp=cmp+1
            child = root * 2 + 1
            if child + 1 <= end and A[child] < A[child + 1]: #for left child
                cmp=cmp+1
                child += 1
            if child <= end and A[root] < A[child]:
                cmp=cmp+1
                A[root], A[child] = A[child], A[root]
                root = child
            else:
                return

    heapify(A)
    end = len(A) - 1
    while end > 0:
        cmp=cmp+1
        A[end], A[0] = A[0], A[end]
        shiftDown(A, 0, end - 1)
        end -= 1

def main():
    start = clock()
    global cmp
    result=[]
    cmp=0
    fin=open("in14_8.txt","r")
    fout=open("out_27_14_8.txt","w")
    data = []
    for line in fin:
        for x in line.split(','):
            data.append (int(x))
    HeapSort(data)
    
    for i in range(0,len(data)):
        result.append(str(data[i]))
    
    fout.write(", ".join(result))
    end = clock()
    time= end - start
    fout.write("\n\n Total execuion time ="+ str(time)+ " seconds")
    fout.write("\n Number of comparisons = "+ str(cmp))
    m=sys.getsizeof(data)+sys.getsizeof(x)+sys.getsizeof(cmp)+sys.getsizeof(fin)+sys.getsizeof(fout)
    fout.write("\n Memory used= "+str(m)+" bytes")
    fin.close()
    fout.close()

main()