Heap Sort

overview

Summary

heap_sort is a comparison-based algorithm that sorts an array using a binary_heap. For ascending order, it uses a max_heap. Two main steps: build_heap in O(n), then repeatedly swap the root with the last element and sift_down to restore the heap. Overall time is O(n log n) in worst and average cases. It is in_place with O(1) extra space and is not_stable. Works well on arrays and is deterministic, unaffected by input order.