heap_sort

with open('sort.txt') as f:
    for lines in f:
        lines = [int(x) for x in lines.split(',')]
arr = lines

def add(x):
    nonlocal heap
    nonlocal hs
    hs += 1
    heap.append(x)
    siftUp(hs)

def siftUp(i):
    nonlocal heap
    if len(heap) < 2: return
    if heap[i] < heap[i//2]:
        heap[i], heap[i//2] = heap[i//2], heap[i]
        siftUp(i//2)

def siftDown(i):
    nonlocal heap
    nonlocal hs
    s = i
    if ((i*2 + 1) < hs and heap[i*2 + 1] < heap[s]): s = i*2 + 1
    if ((i*2 + 2) < hs and heap[i*2 + 2] < heap[s]): s = i*2 + 2
    if s != i:
        heap[i], heap[s] = heap[s], heap[i]
        siftDown(s)

heap = []
hs = -1

for temp in arr:
    add(temp)

result = []

for temp in range(hs, 0, -1):
    result.append(heap[0])
    heap[0] = heap.pop(temp)
    hs -= 1
    siftDown(0)

result += heap

add(arr)
print (result)
input()