레코드 수가 매우 커져도 입력 배열의 초기 정렬 상태와 무관하게 최악 수행시간이 Θ(n log n)인 비교 정렬을 선택하려 한다. 적합한 것은?
정답 4번
합병 정렬은 입력을 반복 분할한 뒤 선형 시간에 병합하므로 최악에도 Θ(n log n)이다. 나머지 세 단순 정렬은 최악 Θ(n²)이므로 ④가 정답이다.
콘텐츠 정보
- 자료 유형
- 편집복원
- 검수 상태
- 내용 검수 완료
- 해설 작성·검수
- 정처LAB 편집 기준
- 최종 검수
- 2026-08-21
합병 정렬은 입력을 반복 분할한 뒤 선형 시간에 병합하므로 최악에도 Θ(n log n)이다. 나머지 세 단순 정렬은 최악 Θ(n²)이므로 ④가 정답이다.