def heap_sort(arr: list):
    """
    Heap sorting a list. Big-O: O(n log n).

    @see https://www.geeksforgeeks.org/heap-sort/
    """
    def heapify(sub: list, rdx: int, siz: int):
        """
        Heapifying range between rdx and size ([rdx:siz]).

        @param sub: a slice of list.
        @param rdx: root/parent index to start.
        @param siz: size of heap.
        """
        largest = ndx = rdx  # assuming the root is the largest
        while ndx < siz:
            l_index = 2 * ndx + 1  # child index at left = 2*i + 1
            r_index = 2 * ndx + 2  # child index at right = 2*i + 2
            # reset largest index if left child exists and is greater than root.
            if l_index < siz and sub[ndx] < sub[l_index]:
                largest = l_index
            # check if right child is greater than the value at the largest index.
            if r_index < siz and sub[largest] < sub[r_index]:
                largest = r_index
            # change root, if needed
            if largest != ndx:
                sub[ndx], sub[largest] = sub[largest], sub[ndx]  # swap
                ndx = largest  # heapify the root.
                continue
            return
        pass

    n = len(arr)
    # build a max heap.
    parent = n // 2 - 1  # the last parent (that can have children)
    for i in range(parent, -1, -1):
        heapify(arr, i, n)

    # extract elements one by one.
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # swap
        heapify(arr, 0, i)

    return arr