문제
다음 중 병합 정렬(Merge Sort)의 특징으로 가장 옳지 않은 것은?
① 분할 정복 기법을 사용하는 정렬 알고리즘이다 ② 최선, 평균, 최악 시간 복잡도가 모두 O(n log n)이다 ③ 추가 메모리 공간 없이 제자리에서 정렬이 가능하다 ④ 안정 정렬로 동일한 값의 상대적 순서를 유지한다
정답
3번
해설
병합 정렬은 분할된 배열을 병합하는 과정에서 임시 배열이 필요하므로 O(n)의 추가 메모리 공간을 사용한다. 따라서 제자리 정렬이 아니다. ① 병합 정렬은 배열을 반으로 나누어 재귀적으로 정렬하는 분할 정복 알고리즘이다. ② 입력 데이터의 초기 상태와 관계없이 항상 O(n log n)의 시간 복잡도를 가진다. ④ 병합 과정에서 동일한 값이 있을 때 앞쪽 배열의 요소를 먼저 선택하므로 안정 정렬이다.