this is a pure python implementation of the heap sort algorithm for doctests run following command python m doctest v heapsort py or python3 m doctest v heapsort py for manual testing run python heapsort py pure implementation of the heap sort algorithm in python param collection some mutable ordered collection with heterogeneous comparable items inside return the same collection ordered by ascending examples heapsort0 5 3 2 2 0 2 2 3 5 heapsort heapsort2 5 45 45 5 2 pure implementation of the heap sort algorithm in python param collection some mutable ordered collection with heterogeneous comparable items inside return the same collection ordered by ascending examples heap_sort 0 5 3 2 2 0 2 2 3 5 heap_sort heap_sort 2 5 45 45 5 2
def heapify(unsorted, index, heap_size):
    largest = index
    left_index = 2 * index + 1
    right_index = 2 * index + 2
    if left_index < heap_size and unsorted[left_index] > unsorted[largest]:
        largest = left_index

    if right_index < heap_size and unsorted[right_index] > unsorted[largest]:
        largest = right_index

    if largest != index:
        unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
        heapify(unsorted, largest, heap_size)


def heap_sort(unsorted):
    
    n = len(unsorted)
    for i in range(n // 2 - 1, -1, -1):
        heapify(unsorted, i, n)
    for i in range(n - 1, 0, -1):
        unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
        heapify(unsorted, 0, i)
    return unsorted


if __name__ == "__main__":
    user_input = input("Enter numbers separated by a comma:\n").strip()
    unsorted = [int(item) for item in user_input.split(",")]
    print(heap_sort(unsorted))