Counterexample Map

정렬 반례는 입력 분포별로 취약 알고리즘을 좁힌다

이미 정렬됨, 역순, 중복 다량, 랜덤 입력을 나눠 보면 병합/퀵/힙 중 무엇을 먼저 의심할지 선명해집니다.

입력 분포	병합 정렬	퀵 정렬	힙 정렬	먼저 볼 로그
[1,2,3,4,5]	안정적	피벗 편향 위험	heapify 비용	재귀 깊이, pivot 위치
[5,4,3,2,1]	예측 가능	최악 분할 가능	최악 O(N log N)	partition 구간 축소
[3,3,3,3]	동일 키 순서 보존	중복 처리 필요	비안정	stable 여부, 비교식
랜덤 대용량	보조 메모리 부담	평균 빠름	캐시 효율 낮음	메모리 사용량, 비교 횟수

정렬/역순 입력퀵 정렬은 피벗이 한쪽으로 치우치는지 재귀 깊이와 partition 구간을 먼저 봅니다.

중복 다량 입력병합 정렬은 안정성을 지키기 쉽고, 퀵 정렬은 동일 키 분할 정책이 중요합니다.

랜덤 대용량 입력평균 성능은 퀵이 강하지만, 병합의 메모리와 힙의 캐시 비용을 함께 봅니다.

핵심: 반례는 “틀리는 알고리즘”이 아니라 “먼저 볼 로그”를 정해 줍니다.