Add Heap Sort Algorithm
Description
Add heap sort algorithm implementation to the sorting algorithms collection.
Implementation Details
- Time complexity: O(n log n) for best, average, and worst cases
- Space complexity: O(1) in-place sorting (O(n) with array copy)
- Not stable
- Uses max-heap data structure
Changes
- Implement
heap_sort()function insort.py - Add
_heapify()helper function - Register in test suite with metadata
- Add to demo program in
main.py
Testing
All 50 tests pass, including:
- Correctness tests on various input cases
- Input immutability test
- Algorithm metadata validation
- Performance benchmark