그만큼 시간 복잡도 병합 정렬은 다음과 같습니다. O(n 로그 n) 둘 다에서 평균 그리고 최악의 경우 . 공간 복잡도 병합 정렬 ~이다 에) . 
| 측면 | 복잡성 |
|---|---|
| 시간 복잡도 | O(n 로그 n) |
| 공간 복잡도 | 에) |
병합 정렬의 시간 복잡도 분석:
다음 용어를 고려하십시오.
T(k) = k개 요소를 정렬하는 데 걸린 시간
M(k) = k개 요소를 병합하는 데 걸린 시간
그러니까 쓸 수 있는 거지
T(N) = 2 * T(N/2) + M(N)
= 2 * T(N/2) + 상수 * N
이러한 N/2 요소는 두 부분으로 더 나뉩니다. 그래서,
T(N) = 2 * [2 * T(N/4) + 상수 * N/2] + 상수 * N
= 4 * T(N/4) + 2 * N * 상수
. . .
= 2케이* 티(N/2케이) + k * N * 상수
하나의 요소가 남을 때까지 최대로 나눌 수 있습니다. 그럼 N/2케이= 1. k = 로그 2 N
T(N) = N * T(1) + N * 로그2N * 상수
= N + N * 로그2N
그러므로 시간복잡도는 O(N * 로그 2 N) .
따라서 최선의 경우, 최악의 경우, 평균의 경우 시간복잡도는 동일합니다.
병합 정렬의 공간 복잡도 분석:
병합 정렬 가지고있다 공간 복잡도 ~의 에) . 크기의 보조 배열을 사용하기 때문입니다. N 입력 배열의 정렬된 절반을 병합합니다. 보조 배열은 병합된 결과를 저장하는 데 사용되며, 입력 배열은 정렬된 결과로 덮어쓰여집니다.