정렬된 N개의 데이터를 처리하는 데 O(Nlog2N)의 시간이 소요되는… | 21년-2회차-정보처리기사-필기 기출문제 상세 페이지

합병정렬(Merge Sort)은 데이터를 반씩 분할해 재귀적으로 정렬한 뒤 병합하는 방식으로, 분할 단계가 $\log_2 N$회 반복되고 각 단계마다 N개의 원소를 병합하므로 시간복잡도가 항상 $O(N\log_2 N)$이다.
반면 버블정렬·선택정렬·삽입정렬은 단순 비교·교환 기반으로 평균 및 최악 시간복잡도가 $O(N^2)$이다.