Sorting Compare
O(N log N) 정렬은 시간보다 선택 책임이 다르다
세 정렬의 차이는 평균 시간보다 안정성, 메모리, 최악 보장, 직접 구현 리스크에서 드러납니다.
정렬
강점
위험
쓸 때
Merge
안정, 최악 보장
O(N) 메모리
동일 키 순서 보존
Quick
평균 빠름
피벗 실패 O(N^2)
분포가 좋고 locality 중시
Heap
제자리, 최악 보장
비안정, 캐시 약함
메모리 제한 + 보장 필요
Merge
안정성과 최악 보장이 강하지만 O(N) 보조 배열이 필요합니다.
Quick
평균이 빠르지만 피벗 실패 시 O(N^2)로 흔들립니다.
Heap
제자리와 최악 보장이 강하지만 비안정이고 캐시 효율이 낮습니다.
최종 선택 질문
안정성이 필수인가?
그렇다면 Merge 또는 검증된 stable sort.
메모리가 제한적인가?
O(N) 보조 배열을 감당 못 하면 Heap/Quick 후보.
최악 보장이 필요한가?
Quick 단독 선택은 피벗 전략을 함께 검증합니다.
직접 구현해야 하는가?
partition, merge, heapify 로그를 따로 남깁니다.