다음 중 배열에 저장된 n개의 레코드를 키의 오름차순으로 정렬하는 알고… | [국회직 9급 컴퓨터일반] 16년 1회차 기출문제 상세 페이지

병합 정렬의 평균 시간 복잡도가 $O(n \log n)$이라는 설명이 옳다.
병합 정렬은 절반씩 나누고 병합하는 과정을 반복하므로 입력 상태와 관계없이 항상 같은 차수의 시간이 걸린다.
힙 정렬의 안정성: 힙 구성과 삭제 중 같은 키의 상대 순서가 바뀔 수 있어 불안정 정렬이다.
퀵 정렬의 최악 복잡도: 분할이 한쪽으로 치우치면 $O(n^2)$이 된다.
이미 정렬된 입력의 병합 정렬: 분할과 병합을 그대로 수행하므로 $O(n \log n)$이다.
삽입 정렬과 퀵 정렬의 비교: 삽입 정렬은 평균 $O(n^2)$이므로 n이 클수록 퀵 정렬보다 느리다.