Heap Sort is an efficient sorting algorithm that leverages a Binary Heap data structure to organize and sort data. It works by first building a heap from the data and then repeatedly extracting the largest (or smallest) element from the heap and rebuilding the heap until all elements are sorted. This method is known for its reliable performance and in-place sorting capabilities, making it a strong choice for handling large datasets without requiring extra memory.

    for i = (n / 2 - 1) down to 0:

        heapify(i)

    for i = n - 1 down to 1:

        swap(0, i)

        heapify(0)