Heap sort (using heapq)

"""
Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It's a classic example of using heaps to sort elements efficiently.

## Time Complexity

The time complexity of the Heap Sort algorithm is O(n log n) in the best, average, and worst-case scenarios. In practice, heap sort is often slower than quicksort, but it is more stable, meaning that elements with equal values appear in the same order in the sorted output as they did in the original input.

Heap Sort consists of two main phases: building the heap and extracting elements from the heap to create the sorted output.

1. Building the Heap:

   - The process of building a max-heap (or min-heap) from an unsorted array involves "heapifying" each element.
   - The time complexity to heapify a single element is O(logn).
   - However, since we start heapifying from the middle of the array and move upwards, the overall time complexity for building the heap is O(n). This is because the work done decreases as we move up the heap. Formally, the complexity can be shown as O(n) through a more detailed analysis of the heapify process over all elements.

2. Extracting Elements:

   - Once the heap is built, the next phase involves extracting the maximum (or minimum) element from the heap and then re-heapifying the remaining elements.
   - Extracting the maximum element takes O(logn) time, and this step is repeated for all n elements.
   - Therefore, the time complexity for this phase is O(nlogn).

Combining both phases, the overall time complexity of Heap Sort is:

O(nlogn)

## Space Complexity

1. In-Place Sorting:

   - Heap Sort is an in-place sorting algorithm, meaning it requires a constant amount of additional space for the algorithm itself (not including the input array).
   - Specifically, the additional space required is O(1).

2. Auxiliary Space:

   - No additional arrays or significant data structures are used during the sorting process, except for a few variables.

Combining both points, the space complexity of Heap Sort is: O(1)

## Summary

Time Complexity: O(nlogn)
Space Complexity: O(1)
"""
import heapq

def heap_sort(nums):
    heapq.heapify(nums)
    sorted_nums = []
    while nums:
        sorted_nums.append(heapq.heappop(nums))
    return sorted_nums

# Example usage
nums = [3, 1, 4, 1, 5, 9, 2, 6, 5]
print(heap_sort(nums))  # Output: [1, 1, 2, 3, 4, 5, 5, 6, 9]