Heap Sort

def heapify(arr, index, size):
		# Initialize largest as root
    largest = index

    left = 2 * index + 1
    right = 2 * index + 2

		# See if left child of root exists and is greater than root
    if left < size and arr[largest] < arr[left]:
        largest = left
		# See if right child of root exists and is greater than root
    if right < size and arr[largest] < arr[right]:
        largest = right

		# Change root, if needed
    if largest != index:
        arr[largest], arr[index] = arr[index], arr[largest]

				# Heapify the root
        heapify(arr, largest, size)


def heap_sort(arr):
    """
    Pure implementation of the heap sort algorithm in Python
    :return: the same collection ordered by ascending order
    """
    n = len(arr)

		# Build a maxheap.
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, i, n)

		# One by one extract elements from the heap
    for i in range(n - 1, 0, -1):
				# Swap
        arr[0], arr[i] = arr[i], arr[0]

        heapify(arr, 0, i)
    return arr