배열을 힙으로 만든 뒤 루트를 하나씩 꺼내면서 정렬하는 방법. 최대 힙이면 루트가 항상 최댓값이니, 꺼낸 것을 뒤에서부터 채우면 오름차순이 완성된다.
힙을 만들고 루트를 꺼내기
먼저 배열 전체를 최대 힙으로 만든다. n/2번째부터 1번까지 거꾸로 heapify를 부르면 O(n)에 끝난다. 그 다음 루트인 최댓값과 맨 끝 원소를 교환한다. 최댓값이 제자리를 찾은 것이다. 힙의 크기를 하나 줄이고 루트에서 heapify를 내리면 O(log n)에 다시 힙이 된다. 교환과 heapify를 n-1번 반복하면 마지막 하나는 저절로 제자리라 정렬이 끝난다.
복잡도와 성질
힙을 만드는 데 O(n), 꺼내는 것을 n번 하는데 각각 O(log n)이니 합쳐서 O(n log n)이고, 합병 정렬처럼 최악에도 흔들리지 않는다. 공간복잡도는 O(1)이다. 배열 안에서 교환만 하므로 제자리 정렬이고, 합병 정렬이 임시 배열을 필요로 하는 것과 대비된다. 루트와 맨 끝을 교환하는 것 자체가 멀리 떨어진 원소를 바꾸는 일이라 안정 정렬은 아니다.
참조 지역성과 인트로소트
세 고급 정렬 중 이론적 성질만 보면 가장 좋아 보인다. 최악이 n log n이고 추가 메모리도 안 쓴다. 그런데 실제로는 퀵 정렬보다 느리다.
참조 지역성이 나쁘기 때문이다. heapify는 인덱스 i에서 2i, 4i로 건너뛰며 배열을 오간다. 배열을 순서대로 훑는 퀵 정렬이나 합병 정렬과 달리 캐시가 계속 빗나간다.
그래서 힙 정렬을 단독으로 쓰기보다는, 퀵 정렬이 최악으로 치달을 때 힙 정렬로 갈아타는 인트로소트 같은 혼합 방식으로 쓰인다.