[자료구조] Heap Sort 개념 (feat. Merge Sort와의 비교)

Merge Sort는 분할 정복 방식으로 배열을 정렬하며, 안정적이고 O(nlogn)의 시간 복잡도를 갖지만, 몇 가지 단점이 있다:

1. 추가 메모리 사용: Merge Sort는 정렬 과정에서 추가적인 메모리 공간이 필요하다. 원본 배열과 동일한 크기의 보조 배열을 생성해야 하므로, 공간 복잡도가 O(n)이다. 이는 메모리 사용이 제한된 환경에서는 큰 단점이 된다.
2. 비연속적 데이터 접근: Merge Sort는 재귀적으로 배열을 분할하고 병합하는 과정에서 비연속적인 메모리 접근이 빈번히 일어난다. 이는 캐시 성능을 저하시킬 수 있으며, 메모리 접근 비용이 큰 환경에서는 성능 저하의 원인이 된다.

Heap Sort는 이러한 Merge Sort의 단점을 다음과 같이 극복한다:

1. 제자리 정렬(In-place Sort): Heap Sort는 추가적인 배열을 필요로 하지 않는다. 주어진 배열 내에서 정렬이 이루어지므로, 추가 메모리 공간이 거의 필요하지 않다. 따라서 공간 복잡도가 O(1)로 매우 효율적이다.
2. 연속적 데이터 접근: Heap Sort는 이진 힙 구조를 이용하여 정렬을 수행하므로, 비교적 연속적인 메모리 접근이 가능하다. 이는 캐시 효율성을 높여, 메모리 접근 비용을 줄이는 데 도움이 된다.
3. 안정성 문제 해결: Heap Sort는 비교 기반 정렬 알고리즘 중 하나로, 요소 간의 순서가 중요하지 않은 경우에도 안정성을 보장할 수 있다. 이는 특정 상황에서는 Merge Sort와 달리 더욱 효율적으로 작동할 수 있다.