[WEEK01] 합병 정렬

합병 정렬(Merge Sort) 은 분할 정복(Divide and Conquer) 알고리즘으로, 배열을 점차적으로 두 부분으로 나누고, 각각을 정렬한 후 합병(merge)하는 방식으로 동작한다.

🚀 동작 과정

1. 배열을 재귀적으로 나눈다

배열을 계속 반으로 나누며, 더 이상 나누어질 수 없을 때까지 반복한다.

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

2. 나누어진 배열을 합병하며 정렬한다

각각의 작은 배열을 정렬하면서 합친다.

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

3. 합병하면서 정렬

각각의 부분 배열을 합병하면서 정렬된 상태로 유지한다.

[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]

결국, 최종적으로 배열은 정렬된 상태가 된다.

💻 코드 구현

def merge(a, left, right):
    if left < right:
        center = (left + right) // 2
        merge(a, left, center)
        merge(a, center+1, right)

        p = j = 0
        i = k = left

        while i <= center:
            buff[p] = a[i]
            p += 1
            i += 1

        while i <= right and j < p:
            if buff[j] <= a[i]:
                a[k] = buff[j]
                j += 1
            else:
                a[k] = a[i]
                i += 1
            k += 1

        while j < p:
            a[k] = buff[j]
            k += 1
            j += 1

def merge_sort(a):
    n = len(a)
    buff = [None] * n
    merge(a, 0, n-1)
    del buff

🔍 코드 분석

1. merge 함수 (배열 합병)

• merge(a, left, right):
  • a: 정렬할 배열
  • left, right: 배열의 왼쪽과 오른쪽 구간의 인덱스
  • center: 배열을 절반으로 나누는 중앙 인덱스
• 재귀적으로 배열을 두 개의 부분 배열로 나누고, 각 부분 배열을 정렬한 후 다시 합병하는 과정

2. 배열을 나누는 부분

• 배열을 두 부분으로 나누어 재귀적으로 호출함
  • merge(a, left, center) → 왼쪽 절반 정렬
  • merge(a, center+1, right) → 오른쪽 절반 정렬

3. 배열을 합병하는 부분

• p, j: 임시 배열 buff에 데이터를 복사하는 데 사용
• i, k: 배열 a에서 데이터를 병합하는 데 사용

4. buff 배열에 왼쪽 부분 복사

• i <= center까지 왼쪽 절반 배열(a[left ... center])의 값을 buff 배열에 복사함

5. 두 부분 배열을 병합하는 부분

• buff 배열과 a 배열을 병합함
• 두 배열에서 가장 작은 값을 비교하여 배열 a에 넣음 (buff는 왼쪽 절반, a는 오른쪽 절반)
• 비교한 후, 해당 값을 배열 a[k]에 넣고, 인덱스를 증가시킴

6. 남은 값 복사

• 왼쪽 절반 배열(buff)에 남아있는 값들이 있으면, 그것을 a[k]에 그대로 복사함
• 이 단계는 a 배열의 오른쪽 절반이 다 처리된 후에 남은 값들을 처리함

7. merge_sort 함수 (메인 함수)

• merge_sort(a) 함수는 전체 배열을 합병 정렬하는 함수
• buff는 임시 배열로, 각 부분 배열을 합병할 때 사용됨
  • buff는 원본 배열을 수정하지 않고 임시로 데이터를 저장하는 공간
• merge(a, 0, n-1)는 배열 전체를 합병 정렬하는 함수 호출
• 마지막에 del buff를 사용해 buff 배열을 메모리에서 제거함

🕓 시간 복잡도

• 시간 복잡도:
  
  • 배열을 계속 반으로 나누는 데 O(log n) 시간이 걸리고, 나눈 배열을 합병하는 데 O(n) 시간이 걸리므로 전체 시간 복잡도는 O(n log n)
• 공간 복잡도:
  • O(n) : buff 배열을 추가로 사용하기 때문에 배열의 크기만큼 공간이 필요함

📌 정리

• 합병 정렬(Merge Sort)은 분할 정복 알고리즘을 사용하여 배열을 두 부분으로 나누고, 각각을 정렬한 후 합병하는 방식으로 동작한다.
• 이 알고리즘은 안정 정렬(stable sort)으로, 같은 값의 요소들이 원래 배열에서의 순서를 유지한다.
• O(n log n)의 시간 복잡도를 가지며, 병합 작업을 위한 추가적인 메모리 공간이 필요하다.