Sorting (2)

이번 글의 흐름:

• Divide-and-Conquer 패러다임과 Merge-Sort의 재귀 구조
• Merge-sort tree로 재귀 구조를 시각화하고, 트리의 height를 정확히 계산하는 법
• 실제 merge 연산(두 포인터 방식)
• 이 모든 걸 합쳐서 O(n log n) 시간복잡도가 나오는 이유
• Heap-Sort와 달리 O(n) 추가 공간이 필요한 이유 (in-place가 아님)

---

1. Divide-and-Conquer란?

많은 알고리즘이 따르는 3단계 패턴이다.

1. Divide: 문제를 더 작은 부분 문제(subproblem)들로 나눈다
2. Recur: 각 부분 문제를 (재귀적으로) 푼다
3. Conquer: 부분 문제들의 답을 합쳐서 원래 문제의 답을 만든다

Merge-Sort는 이 패턴을 정렬에 그대로 적용한다.

• Divide: 배열을 반으로 나눈다 (왼쪽 절반, 오른쪽 절반)
• Recur: 각 절반을 재귀적으로 Merge-Sort한다
• Conquer(merge): 정렬된 두 절반을 합쳐서 하나의 정렬된 배열로 만든다
• base case: 원소가 1개(또는 0개)인 배열은 이미 정렬된 것으로 본다

---

2. Merge-Sort Tree로 보는 재귀 구조

2.1 예제: [7,2,9,4,3,8,6,1]

Divide 단계 (위 -> 아래로 반씩 나눔)

                          [7,2,9,4,3,8,6,1]
                          /                \
                  [7,2,9,4]                [3,8,6,1]
                  /       \                /       \
              [7,2]      [9,4]          [3,8]      [6,1]
              /   \       /   \          /   \       /   \
            [7]   [2]   [9]   [4]      [3]   [8]   [6]   [1]

8개짜리 배열이 4개 -> 2개 -> 1개로, 매 레벨마다 정확히 절반씩 줄어든다.

Conquer(merge) 단계 (아래 -> 위로 합치기)

            [7]   [2]   [9]   [4]      [3]   [8]   [6]   [1]
              \   /       \   /          \   /       \   /
              [2,7]      [4,9]          [3,8]      [1,6]
                  \       /                  \       /
                  [2,4,7,9]                  [1,3,6,8]
                          \                  /
                          [1,2,3,4,6,7,8,9]

각 leaf(원소 1개)는 "이미 정렬됨"으로 시작하고, 한 레벨씩 올라가면서 두 개의 정렬된 배열을 하나의 정렬된 배열로 합치는(merge) 작업이 일어난다.

같은 트리를 두 방향으로 훑는다고 생각하면 된다 - Divide는 위에서 아래로(큰 문제를 계속 쪼갬), Merge는 아래에서 위로(작은 답들을 합쳐서 큰 답을 만듦).

2.2 트리의 height - 헷갈리기 쉬운 부분

n=8 트리를 보면 레벨이 다음과 같다.

레벨0: 크기8  (1개)   [7,2,9,4,3,8,6,1]
레벨1: 크기4  (2개)
레벨2: 크기2  (4개)
레벨3: 크기1  (8개, leaf)

여기서 레벨(층)은 0~3까지 총 4개가 있다. 그런데 height(높이)는 "root에서 leaf까지 거치는 edge(간선)의 개수"이므로 0->1->2->3, 즉 3이다. log2(8)=3과 일치한다.

즉 "레벨의 개수 = height + 1"이지, "height = log2(n) + 1"이 아니다. n=16이라면:

레벨0: 크기16 (1개)
레벨1: 크기8  (2개)
레벨2: 크기4  (4개)
레벨3: 크기2  (8개)
레벨4: 크기1  (16개, leaf)

 레벨은 0~4까지 5개이지만, height는 4(=log2(16), root->leaf까지 edge 4개)다. 처음엔 "log2(16)=4번 쪼개야 한다"는 계산에 추가로 1을 더해 height=5라고 잘못 생각하기 쉬운데, 그 "+1"은 height가 아니라 레벨의 개수에 적용되는 보정이다.

2.3 일반화

• 트리의 height = log2(n) = O(log n)
• 레벨의 개수 = height + 1 = O(log n)
• leaf의 개수 = n
• 각 레벨에서 처리할 원소의 총합은 항상 n개다 (레벨이 내려갈수록 배열 개수는 2배씩 늘지만 각 배열 크기는 절반씩 줄어들기 때문).

---

3. Merge 연산 - 두 포인터(two-pointer) 방식

merge(A, B)는 이미 정렬된 두 배열 A, B를 합쳐서 하나의 정렬된 배열을 만드는 연산이다. 핵심 아이디어: A와 B의 맨 앞 원소끼리만 비교하면 된다 - 둘 다 정렬돼있으므로, 두 맨 앞 원소 중 더 작은 게 전체에서도 가장 작다.

• A, B 각각 포인터(i, j)를 맨 앞에 둔다
• A[i]와 B[j]를 비교, 더 작은 쪽을 결과에 넣고 그 포인터를 한 칸 전진
• 한쪽이 끝나면, 남은 쪽을 그대로 결과 뒤에 이어붙인다

3.1 예제: merge([2,4,7,9], [1,3,6,8])

A=[2,4,7,9] (i=0)   B=[1,3,6,8] (j=0)   결과=[]
2 vs 1 -> 1 작음 -> [1]              (j=1)
2 vs 3 -> 2 작음 -> [1,2]            (i=1)
4 vs 3 -> 3 작음 -> [1,2,3]          (j=2)
4 vs 6 -> 4 작음 -> [1,2,3,4]        (i=2)
7 vs 6 -> 6 작음 -> [1,2,3,4,6]      (j=3)
7 vs 8 -> 7 작음 -> [1,2,3,4,6,7]    (i=3)
9 vs 8 -> 8 작음 -> [1,2,3,4,6,7,8]  (j=4, B 끝)
B 끝났으니 A의 남은 원소(9)를 그대로 추가 -> [1,2,3,4,6,7,8,9]

3.2 예제: merge([3,8], [1,6])

A=[3,8] (i=0)   B=[1,6] (j=0)   결과=[]
3 vs 1 -> 1 작음 -> [1]       (j=1)
3 vs 6 -> 3 작음 -> [1,3]     (i=1)
8 vs 6 -> 6 작음 -> [1,3,6]   (j=2, B 끝)
B 끝났으니 A의 남은 원소(8)를 그대로 추가 -> [1,3,6,8]

 두 예제 모두 A와 B의 크기 합이 k라면 merge는 O(k)임을 보여준다 - 모든 원소를 정확히 한 번씩만 들여다보고 결과에 배치하기 때문이다.

---

4. 시간복잡도 - 왜 O(n log n)인가

2.3에서 본 "각 레벨에서 처리할 원소의 총합은 항상 n개"가 핵심이다. n=8 예제로 merge 단계(아래->위)의 작업량을 보자.

레벨3(크기1) -> 레벨2: merge 4번, 각각 크기1+1=2 -> 4 x O(2) = O(8) = O(n)
레벨2(크기2) -> 레벨1: merge 2번, 각각 크기2+2=4 -> 2 x O(4) = O(8) = O(n)
레벨1(크기4) -> 레벨0: merge 1번, 크기4+4=8     -> 1 x O(8) = O(8) = O(n)

각 레벨에서 일어나는 merge들의 작업량을 다 더하면 항상 O(n)이다 - merge의 개수는 절반씩 줄어들지만, 각 merge가 처리하는 크기는 그만큼 2배씩 커지므로 서로 상쇄된다.

 

그리고 레벨의 개수는 2.3에서 본 대로 O(log n)이다.

전체 시간 = (레벨당 작업량 O(n)) x (레벨 개수 O(log n)) = O(n log n)

 

---

5. 공간복잡도 - Heap-Sort와의 차이

 (1)의 Heap-Sort는 swap만으로 동작해서 in-place(추가 공간 O(1))였다. 반면 Merge-Sort의 merge 연산은 결과를 담을 새 배열이 필요하다 - 두 포인터로 비교하면서 "새로운 자리"에 채워나가야 하므로 원본 자리에 그대로 덮어쓸 수 없다. 그래서 Merge-Sort는 O(n)의 추가 공간이 필요하고, in-place가 아니다.

	시간복잡도	공간복잡도	in-place
Heap-Sort	O(n log n)	O(1)	예
Merge-Sort	O(n log n)	O(n)	아니오

 같은 O(n log n)이라도 "어디서 비용을 지불하는가"가 다르다 - Heap-Sort는 시간 대신 down-heap이라는 추가 연산으로 메모리를 아끼고, Merge-Sort는 merge를 위한 임시 공간을 대가로 더 단순한 구조를 가진다.

---

마무리

이번 글의 흐름: Divide-and-Conquer 패러다임 -> Merge-Sort tree로 재귀 구조 시각화(divide는 위->아래, merge는 아래->위) -> 두 포인터 merge 연산 -> "레벨당 O(n)" 논리로 O(n log n) 도출 -> O(n) 추가 공간이 필요한 이유.

 

핵심 정리:

• height = log2(n), 레벨 개수 = height+1. n=16이면 height=4, 레벨 5개, leaf 16개 - height에 함부로 +1 하지 않기
• merge(A,B)는 두 포인터로 맨 앞 원소끼리만 비교, O(|A|+|B|)
• 각 레벨의 merge 작업량 총합은 항상 O(n) -> 레벨 O(log n)개 -> 전체 O(n log n)
• Merge-Sort는 O(n) 추가 공간 필요 (Heap-Sort는 O(1))