퀵 정렬 vs 병합 정렬 vs 힙 정렬

상황에 따라 가장 적절한 정렬 알고리즘을 선택해야 한다.

• 퀵 정렬(Quick Sort) → 일반적으로 가장 빠른 정렬 (O(n log n), 평균적)
• 병합 정렬(Merge Sort) → 항상 안정적인 성능 보장 (O(n log n), 최악 포함)
• 힙 정렬(Heap Sort) → 추가 메모리 없이 정렬 가능 (O(n log n), 안정 정렬 X)

상황	추천 정렬 알고리즘
일반적인 경우 (랜덤 데이터)	퀵 정렬 (Quick Sort)
이미 정렬된 데이터	병합 정렬 (Merge Sort)
Stable Sort(안정 정렬)이 필요할 때	병합 정렬 (Merge Sort)
추가 메모리 없이 정렬해야 할 때	힙 정렬 (Heap Sort)
우선순위 정렬이 필요할 때	힙 정렬 (Heap Sort)
Linked List를 정렬해야 할 때	병합 정렬 (Merge Sort)

---

퀵 정렬(Quick Sort) - "가장 일반적인 정렬"

✅ 랜덤한 데이터에서 가장 빠름 (O(n log n), 평균)
✅ 추가 메모리 사용 없이 제자리 정렬 (In-place, O(log n) 공간)
✅ 실무에서 많이 사용됨 (Python의 sorted()도 퀵 정렬 원리 일부 사용)

❌ 하지만, 이미 정렬된 데이터에서는 O(n²) 발생 가능 → 피벗 선택 중요!\

 

퀵 정렬이 적절한 경우

• 일반적인 데이터 정렬 (대부분의 경우 최적)
• 랜덤하게 섞인 데이터 (O(n log n))
• 추가 메모리 없이 빠르게 정렬해야 할 때

2024.06.26 - [데이터 사이언스/알고리즘] - 퀵 정렬

---

병합 정렬(Merge Sort) - "안정적이고 항상 O(n log n) 보장"

✅ 최악의 경우에도 O(n log n) 보장 (정렬된 데이터에서도 성능 유지)
✅ Stable Sort(안정 정렬) → 동일한 값을 가진 요소의 순서를 유지함
✅ Linked List 정렬에도 적합 (추가 메모리를 써도 노드 이동이 쉽기 때문)

❌ 하지만, O(n) 추가 메모리 사용 → 공간 효율성 낮음

 

병합 정렬이 적절한 경우

• 이미 정렬된 데이터에서도 성능이 유지되어야 할 때
• Stable Sort(안정 정렬)이 필요한 경우
• Linked List 정렬이 필요한 경우

2025.01.20 - [데이터 사이언스/알고리즘] - 병합 정렬 (Merge Sort)

---

3. 힙 정렬(Heap Sort) - "추가 메모리 없이 정렬 가능"

✅ 추가 메모리 없이 O(1) 공간으로 정렬 가능 → 대용량 데이터 정렬에 유리
✅ 최악의 경우에도 O(n log n) 보장
✅ 우선순위 큐(Priority Queue)와 잘 어울림

❌ 하지만, 실제 성능은 퀵 정렬보다 느릴 수 있음 (캐시 효율성 낮음)

 

힙 정렬이 적절한 경우

• 추가적인 메모리 사용 없이 정렬이 필요한 경우
• 우선순위 정렬이 필요한 경우 (예: Top-K 요소 찾기, Priority Queue)
• 대용량 데이터에서 안정적인 O(n log n) 성능이 필요한 경우

2025.01.20 - [데이터 사이언스/알고리즘] - 힙 정렬 (Heap Sort)