# 병합 정렬 ## 목차 --- 1. 무엇? 2. 특징? 3. 알고리즘 ## 1. 무엇? --- 분할 정복 기법 알고리즘의 하나. 1. 리스트의 길이가 1이하는 정렬된 것. 그렇지 않다면 2. 분할(divide) - 정렬되지 않은 리스트를, 절반으로 나눔 3. 정복(conquer) - 각 부분 리스트를, 재귀적으로 병합 정렬 4. 결합(combine) - 두 부분 리스트를, 하나의 정렬된 리스트로 만듬 5. 복사(copy) - 임시 리스트에 정렬 결과를 원래 리스트에 복사 ## 2. 특징? --- - 빠름, 시간 복잡도 O(nlogn) - 안정 정렬(같은 값의 원소 순서 유지 O) - 추가 메모리 필요, 공간 복잡도 O(n) ## 3. 알고리즘 ---  ### 소스코드 ``` mergeSort(A[ ], start, end) { if (start < end) then { // 정렬할 부분의 크기가 1 이하이면, 그냥 리턴한다. middle ← (start + end)/2; // (1) start, end의 중간 지점 계산 mergeSort(A, start, middle); // (2) 중간 지점을 기준으로 앞부분 정렬 mergeSort(A, middle+1, end); // (3) 중간 지점을 기준으로 뒷부분 정렬 merge(A, start, middle, end); // (4) 병합 } } merge(A[ ], start, middle, end) { 정렬되어 있는 두 배열 A[start ... middle]와 A[middle+1 ... end]을 합하여 정렬된 하나의 배열 A[start ... end]을 만든다. } ```