병합정렬(Merge Sort) 알고리즘

병합정렬 알고리즘은 Divide and Conquer 알고리즘의 원칙을 기반으로 합니다.

정렬되지 않은 데이터는 divide됩니다. 그리고 비교를 거쳐 정렬되게 됩니다.

---

Divide and Conquer

Divide and Conquer은 배열을 반반씩 나누며 하나가 될때까지 divide과정을 거친다.

위의 예시에서는 6, 5, 12, 10, 9, 1 이 될때까지 divide를 한다.

그리고 Conquer(정복)하는 과정에서 큰 수를 오른쪽으로 보내며 병합한다.

왼쪽의 첫 번째 요소를, 오른쪽 배열의 모든요소와 비교하여 더 큰게 없다면 Merge할 배열의 인덱스에 차곡차곡 넣는다.

그다음에는 오른쪽 배열의 요소를 왼쪽 배열과 비교하는 식으로 차례차례 반복한다.

---

MergeSort알고리즘

MergeSort(A, p, r):
    if p > r 
        return
    q = (p+r)/2
    mergeSort(A, p, q)
    mergeSort(A, q+1, r)
    merge(A, p, q, r)

A는 배열, p는 배열의 시작인덱스, r은 배열의 끝 인덱스이다.

 

if p >= r
        return

만약 p가 r보다 크거나 같다면, 배열의 크기가 1이거나 1이하이므로 분할할 필요가 없다. 따라서 return

 

q = (p + r) / 2

q는 중간 인덱스이다. (p + r) / 2를 통해 중간 인덱스를 계산한다.

 

mergeSort(A, p, q)
mergeSort(A, q + 1, r)

mergeSort(A, p, q) 는 배열의 첫 번째 절반 A[p]부터A[q]를 정렬한다.

mergeSort(A, q+1, r)는 배열의 두 번째 절반 A[q+1]부터 A[r]를 정렬한다.

 

merge(A, p, q, r)

분할된 두개의 배열을 merge하여 하나의 정렬된 배열로 만듭니다.

---

 병합정렬 예시

[38, 27, 43, 3, 9, 82, 10]

1. Divide(분할)

[38, 27, 43, 3]   [9, 82, 10]

[38, 27]   [43, 3]         [9, 82]   [10]

[38]      [27]       [43]       [3]       [9]       [82]        [10]

 

2. Conquer(정복)

38과 27을 병합 [27, 38]

43과 3을 병합 [3, 43]

9와 82을 병합 [9, 82]

10은 그대로 [10]

 

3. Merge(병합)

[27, 38]과 [3, 43]을 병합 [3, 27, 38, 43]

[9, 82]과  [10]을 병합 [9, 10, 82]

최종적으로 [3, 27, 38, 43]과 [9, 10, 82]를 병합.

[3, 9, 10, 27, 38, 43, 82]