Heap Sort Implementation

Implement an in-place heap sort that returns a sorted list from any list of comparable elements.

heap sorting in-place comparison

Write a function `heap_sort` that takes a list `arr` of comparable elements and returns a new list containing the same elements sorted in non-decreasing order. The algorithm must use a heap-based approach: build a max-heap from the input and repeatedly extract the maximum. Your implementation must not use built-in sorting functions like `sorted()` or `list.sort()`, and must not use external libraries (only the Python standard library is allowed). The function should not modify the input list; it should return a new sorted list.

Constraints

Input list length: 0 <= len(arr) <= 10^5. Elements must be mutually comparable (e.g., all ints, all floats, or all strings). The solution should run in O(n log n) time and O(1) extra space (besides the output list).

Example

>>> heap_sort([3, 1, 2])
[1, 2, 3]
>>> heap_sort([5, 5, 5, 1])
[1, 5, 5, 5]
>>> heap_sort([])
[]

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Build a max-heap from the input list by heapifying from the middle down to the root.

To sort in place, swap the root (max) with the last unsorted element, then reduce the heap size and sift down.

The sift-down operation compares a node with its children and swaps with the larger child if needed.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.