다음 정렬(sorting) 기법들 중 평균 시간 복잡도(average … | [법원직 9급 전산·사서 컴퓨터일반] 26년 1회차 기출문제 상세 페이지

평균 시간 복잡도가 $O(n \log n)$이 아닌 것은 삽입 정렬이다.
삽입 정렬은 각 원소를 앞쪽 정렬 구간과 비교해 끼워 넣으므로 평균 $O(n^2)$이다.
병합 정렬: 절반씩 나누어 병합하므로 평균과 최악 모두 $O(n \log n)$이다.
힙 정렬: 삭제와 재정렬을 원소 수만큼 반복해 평균 $O(n \log n)$이다.
퀵 정렬: 최악은 $O(n^2)$이지만 평균은 $O(n \log n)$이다.