Page 254 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)
P. 254
a 배열 a의 앞부분을 배열 buff에 복사합니다.
left center right
a 1 3 4 6 11 12 2 3 5 6 7 8
buff 1 3 4 6 11 12
０ １ ２ ３ ４ ５ ❻
p
b 배열 a의 뒷부분과 배열 buff를 배열 a에 병합합니다.
병합하기 전 a 1 3 4 6 11 12 2 3 5 6 7 8
a 1 2 3 3 4 5 6 6 7 8 7 8
buff 1 3 4 6 11 12
c 배열 buff의 나머지 요소를 배열 a에 복사합니다.
a 1 2 3 3 4 5 6 6 7 8 11 12
buff 1 3 4 6 11 12
[그림 6-32] 병합 정렬에서 배열의 앞부분과 뒷부분의 병합 과정
배열 병합의 시간 복잡도는 O(n)이고 데이터의 요소 개수가 n개일 때, 병합 정렬의 단계는
log n만큼 필요하므로 전체 시간 복잡도는 O(n log n)이라고 할 수 있습니다. 병합 정렬은 서
로 떨어져 있는 요소를 교환하는 것이 아니므로 안정적인 정렬 방법이라고 할 수 있습니다.
254 C 알고리즘
