def sift(li,low,high):
    temp = li[low]
    i = low
    j = 2*i+1
    while j <= high:
        if j+1 <= high and li[j] < li[j+1]:
            j += 1
        if temp < li[j]:
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:
            break
    li[i] = temp
def heap_sort(li):
    # 建堆
    n = len(li) - 1
    i = (n - 1)//2
    while i >= 0:
        sift(li,i,n)
        i -= 1
    while n >= 0:
        li[0],li[n] = li[n],li[0]
        n -= 1
        sift(li,0,n)
        
class Solution:
    def MySort(self , arr: List[int]) -> List[int]:
        # write code here
        heap_sort(arr)
        return arr