힙 정렬의 수행시간은 O(nlogN) 이다. 수행시간은 병합정렬과 비슷하고 삽입정렬과는 내부 정렬이라는 점이 같다. 따라서 상수 개의 원소를 초과해서 배열 밖에 저장하는 일은 없다.힙 정렬은 상기의 두 정렬의 장점을 혼합한 것이다.(이진) 힙 자료구조는 완전 이진트리로