Time and Space Complexity

시간 복잡도:

• 최선, 평균, 최악의 경우: O(n log n)
  • 힙을 구성하는 데는 O(n)이 소요되며, n번의 추출 각각은 sift-down을 위해 O(log n)의 비용이 듭니다. 성능을 저하시키는 최악의 입력 사례는 없습니다.

공간 복잡도:

• O(1)
  • Heap Sort는 원래 배열 내부에서 요소들을 재배치하며, 일정한 양의 추가 메모리만 필요로 합니다.

요약:

• Heap Sort는 보장된 O(n log n) 실행 시간과 O(1)의 추가 공간을 결합한 것으로, 이는 Merge Sort와 Quick Sort가 모두 제공하지는 못하는 조합입니다.
• 안정 정렬(stable)이 아니라는 점(동일한 요소들의 상대적 순서가 바뀔 수 있음)이 주요 트레이드오프입니다.