heapsort.py

def heapsort(l):
    heapify(l)

    for j in range(len(l) - 1, 0, -1):
        l[0], l[j] = l[j], l[0]
        i = 0
        last = j - 1
        while last >= i * 2 + 1:
            r = i * 2 + 1
            cur_down = i
            if l[r] > l[cur_down]:
                cur_down = r
            if last > r and l[r + 1] > l[cur_down]:
                cur_down = r + 1
            if cur_down == i:
                break

            l[i], l[cur_down] = l[cur_down], l[i]
            i = cur_down

def heapify(l):
    start = (len(l) - 2) // 2
    last = len(l) - 1
    while start >= 0:
        i = start
        while last >= i * 2 + 1:
            r = i * 2 + 1
            cur_down = i
            if l[r] > l[cur_down]:
                cur_down = r
            if last > r and l[r + 1] > l[cur_down]:
                cur_down = r + 1
            if cur_down == i:
                break

            l[i], l[cur_down] = l[cur_down], l[i]
            i = cur_down
        start -= 1