algorithm - Ternary heapsort in python 2.7 -

i trying implement ternary heap sort, every parent of heap has 3 children, can not code return sorted list. think may making logical error somewhere can not spot it, fixing code appreciated.

def swap(i, j):     sqc[i], sqc[j] = sqc[j], sqc[i]  def heapify(end,i):     l=3 * (i + 1)     m=3 * (i + 2)     r=3 * (i + 3)     max=i     if l < end , sqc[i] < sqc[l]:         max = l     if r < end , sqc[max] < sqc[r]:         max = r     if m < end , sqc[max] < sqc[m]:         max = m     if max != i:         swap(i, max)         heapify(end, max)  def heap_sort():     end = len(sqc)     start = end / 2 - 1     in range(start, -1, -1):         heapify(end, i)     in range(end-1, 0, -1):         swap(i, 0)         heapify(i, 0)  sqc = [2, 7, 1, -2, 56, 5, 3] heap_sort() print(sqc) 

[7, 1, -2, 56, 5, 2, 3] returned, out of order.

code

def heapsort3(a):     def sift(start, count):         root = start         while root * 3 + 1 < count:             r3 = root * 3             upper = min(count - r3, 4)             children = list(range(r3 + 1, r3 + upper))             min_child = min((a[i], i) in children)             v, = min_child             if a[root] > a[i]:                 a[root], a[i] = a[i], a[root]                 root =             else:                 break     count = len(a)     start in reversed(range(count // 3 + 2)):         sift(start, count)     end in reversed(range(count)):         a[end], a[0] = a[0], a[end]         sift(0, end)     return 

test on sorted , reverse-sorted

for in range(2, 25):     print '-' * 30     data = list(range(i))     sorted_data = heapsort3(data)     print i, sorted_data     data = list(reversed(range(i)))     sorted_data = heapsort3(data)     print i, sorted_data 

test on shuffled data

from random import shuffle in range(1, 100):     print '-' * 30,     expected = list(reversed(range(i)))     _ in range(5000):         data = list(range(i))         shuffle(data)         sorted_data = heapsort3(data)         assert sorted_data == expected 

reference

adapted this code. sort of.