12 — 병합 정렬

람다와 제네릭이 카드 8장을 앞에 두고 혼자 정렬하기 버거워하자, 제네릭이 더미를 반으로 갈라 한쪽씩 나눠 들고 "절반씩 나눠서 각자 정렬한 다음 합치자!"라고 제안하고, 돌핀쌤이 "그게 바로 분할정복, 오늘 배울 병합 정렬이에요"라고 안내하는 도입

🙋‍♀️ 람다: "카드 8장을 순서대로 줄 세우려니 너무 헷갈려요…"

🙋‍♂️ 제네릭: "그럼 절반은 내가 맡을게! 너는 왼쪽, 나는 오른쪽을 각자 정렬한 다음 합치자."

🐬 돌핀쌤: "두 친구가 방금 발견한 게 바로 오늘 배울 병합 정렬이에요. 큰 문제를 반으로 나누고(분할), 각각 정렬한 다음 다시 합치는(merge) 거죠. 10차시 재귀랑 8차시 정렬이 한자리에 모이니 조금 어려울 수 있어요. 천천히 같이 따라가 봐요."

🎯 오늘 완성할 코드는?

오늘 만들 건 병합 정렬이에요. 리스트를 반으로 계속 쪼갰다가, 정렬하면서 다시 합치는 방법으로 숫자를 작은 순서대로 줄 세우는 코드예요.

먼저 완성된 모습부터 볼게요. 지금은 이해 안 돼도 괜찮아요. 아래에서 한 줄씩 천천히 뜯어볼 거예요.

def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:   # 왼쪽이 작거나 같으면
            result.append(left[i])
            i += 1
        else:                     # 오른쪽이 작으면
            result.append(right[j])
            j += 1
    result += left[i:]    # 왼쪽 남은 것 붙이기
    result += right[j:]   # 오른쪽 남은 것 붙이기
    return result

def merge_sort(arr):
    if len(arr) <= 1:      # 기저 조건
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # 왼쪽 재귀 정렬
    right = merge_sort(arr[mid:])   # 오른쪽 재귀 정렬
    return merge(left, right)

numbers = [38, 27, 43, 3, 9, 82, 10, 1]
print(merge_sort(numbers))   # [1, 3, 9, 10, 27, 38, 43, 82]

실행하면 이렇게 나와요.

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

뒤죽박죽이던 [38, 27, 43, 3, 9, 82, 10, 1] 이 작은 순서대로 줄을 섰죠?

🐬 돌핀쌤: "함수가 두 개라 처음엔 길어 보이지만, 하는 일은 딱 두 가지예요. 반으로 나누기(merge_sort) 와 합치기(merge). 지금부터 이 코드가 왜 정렬을 해내는지 하나씩 풀어볼게요."

💡 어떻게 풀까? — 반으로 나눠 각자 정렬하고 합치기

카드 8장을 혼자 정렬하기 힘들면, 절반을 친구에게 나눠주고 각자 정렬한 다음 합치면 돼요. 이게 병합 정렬의 핵심이에요.

리스트를 반으로 계속 쪼개는 걸 분할, 정렬된 조각을 다시 하나로 모으는 걸 합치기(merge) 라고 해요. 이렇게 "나눠서 풀고 합친다"는 방법을 분할정복이라고 불러요.

그런데 합치기에는 한 가지 비밀이 있어요. 이미 정렬된 두 줄을 합칠 때는, 각 줄의 맨 앞 사람끼리만 비교하면 된다는 거예요.

왼쪽 줄: [130, 145, 160]
오른쪽 줄: [135, 150, 155]

맨 앞끼리 비교 → 130 vs 135 → 130 먼저
맨 앞끼리 비교 → 145 vs 135 → 135 먼저
맨 앞끼리 비교 → 145 vs 150 → 145 먼저
...최종: [130, 135, 145, 150, 155, 160]

각 줄이 이미 정렬돼 있으니, 맨 앞만 비교해도 다음에 나올 가장 작은 값을 고를 수 있어요. 맨 위 코드의 merge 함수가 바로 이 일을 해요.

🙋‍♂️ 제네릭: "두 줄을 통째로 다시 정렬하는 게 아니라, 맨 앞만 보면 되는 거군요!"

🔍 코드 한 줄씩 뜯어보기

이제 맨 위에서 본 완성 코드를 한 줄씩 볼게요. 함수가 두 개라 merge_sort(나누기)부터 보고, merge(합치기)를 볼게요.

① 더 이상 못 나누면 그대로 돌려줘요 (기저 조건)

    if len(arr) <= 1:      # 기저 조건
        return arr

원소가 1개(또는 0개) 인 리스트는 이미 정렬된 거예요. 더 나눌 수 없으니 그대로 돌려줘요. 이게 재귀를 멈추는 기저 조건이에요.

💡 == 1 이 아니라 <= 1 인 이유: 빈 리스트 [] 가 들어와도 멈춰야 해요. == 1 만 쓰면 빈 리스트일 때 멈추지 못하고 끝없이 자기 자신을 불러요(무한 재귀).

② 반으로 나눠 각각 또 정렬해요 (재귀)

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # 왼쪽 재귀 정렬
    right = merge_sort(arr[mid:])   # 오른쪽 재귀 정렬

가운데(mid)를 기준으로 arr[:mid](왼쪽 절반)와 arr[mid:](오른쪽 절반)로 나눠요. 그리고 각 절반을 다시 merge_sort에 넣어요. 자기 자신을 또 부르는 재귀예요. 이렇게 원소가 1개가 될 때까지 계속 반으로 쪼개져요.

③ 정렬된 두 조각을 합쳐요

    return merge(left, right)

left 와 right 는 각각 이미 정렬이 끝난 조각이에요. 이 둘을 merge 로 합치면 정렬된 하나의 리스트가 돼요.

④ 맨 앞끼리 비교해서 작은 것부터 담아요 (merge)

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:   # 왼쪽이 작거나 같으면
            result.append(left[i])
            i += 1
        else:                     # 오른쪽이 작으면
            result.append(right[j])
            j += 1
    result += left[i:]    # 왼쪽 남은 것 붙이기
    result += right[j:]   # 오른쪽 남은 것 붙이기

i 는 왼쪽 줄에서 볼 위치, j 는 오른쪽 줄에서 볼 위치예요. 두 줄의 맨 앞(left[i], right[j])을 비교해서 작은 쪽을 result에 담고, 담은 쪽의 위치만 한 칸 옮겨요. 이렇게 위치 두 개를 두고 비교하는 방법을 두 포인터라고 해요.

💡 while 이 끝나는 건 한쪽 줄이 다 떨어졌을 때예요. 그럼 다른 쪽엔 아직 값이 남아 있죠. 남은 쪽은 이미 정렬돼 있으니 result += left[i:] / result += right[j:] 로 통째로 뒤에 붙이면 돼요. left[i:] 는 "i번 위치부터 끝까지 남은 조각"이에요.

⑤ 전체가 어떻게 굴러가는지 — `[38, 27, 43, 3, 9, 82, 10, 1]`

먼저 위에서 아래로 계속 반으로 쪼개요. 원소가 1개가 되면 멈춰요.

[38, 27, 43, 3, 9, 82, 10, 1]
[38, 27, 43, 3]       [9, 82, 10, 1]
[38, 27]  [43, 3]    [9, 82]  [10, 1]
[38][27]  [43][3]   [9][82]  [10][1]   ← 1개씩 = 더 못 나눔

이제 아래에서 위로 두 개씩 합쳐요. 합칠 때마다 정렬돼요.

[38][27]  [43][3]   [9][82]  [10][1]
[27,38]   [3,43]   [9,82]   [1,10]      ← 두 개씩 합치기
   [3,27,38,43]      [1,9,10,82]        ← 또 합치기
   [1, 3, 9, 10, 27, 38, 43, 82]        ← 정렬 완료!

합치는 한 칸을 자세히 볼게요. [27, 38] 과 [3, 43] 을 합치는 과정이에요.

left = [27, 38]   right = [3, 43]
  맨 앞 비교: 27 vs 3  → 3이 작음   → result = [3]
  맨 앞 비교: 27 vs 43 → 27이 작음  → result = [3, 27]
  맨 앞 비교: 38 vs 43 → 38이 작음  → result = [3, 27, 38]
  왼쪽 다 씀 → 오른쪽 남은 [43] 통째로 붙임 → result = [3, 27, 38, 43] ✓

🙋‍♀️ 람다: "나누기는 위에서 아래로, 합치기는 아래에서 위로 가네요! 맨 앞끼리만 비교했는데 딱 정렬됐어요."

✍️ 직접 완성해보기

이제 빈칸을 채워 직접 완성해봐요. 위에서 본 그대로예요.

def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] ___ right[j]:      # 왼쪽이 작거나 같으면 (<=)
            result.append(left[i])
            i += 1
        else:                         # 오른쪽이 작으면
            result.append(right[j])
            j += 1
    result += left[___:]              # 왼쪽 남은 것 붙이기 (i)
    result += right[j:]               # 오른쪽 남은 것 붙이기
    return result

def merge_sort(arr):
    if len(arr) ___ 1:                # 기저 조건 (<=)
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])      # 왼쪽 재귀 정렬
    right = merge_sort(arr[mid:])     # 오른쪽 재귀 정렬
    return merge(left, right)

numbers = [38, 27, 43, 3, 9, 82, 10, 1]
print(merge_sort(numbers))   # [1, 3, 9, 10, 27, 38, 43, 82]

🐬 돌핀쌤: "막히면 위 '코드 한 줄씩 뜯어보기'로 다시 올라가서 확인해요. 다 채웠으면 맨 위 🎯 완성 코드와 비교해보세요. 정답을 외우는 게 아니라 왜 그런지 떠올리는 게 진짜 공부예요."

📌 오늘 배운 것

개념	설명
병합 정렬	반으로 계속 나눴다가(분할) 정렬하며 다시 합치는(merge) 정렬
분할정복	"나눠서 풀고 합친다"는 문제 해결 방법
기저 조건	`len(arr) <= 1` — 원소 1개 이하면 이미 정렬됨, 재귀 멈춤
merge(두 포인터)	두 줄의 맨 앞(`left[i]`, `right[j]`)을 비교해 작은 것부터 담기
남은 것 붙이기	한쪽이 끝나면 `result += left[i:]` / `right[j:]` 로 통째로 붙임

🐬 돌핀쌤: "반으로 나누기, 맨 앞끼리 비교해 합치기, 남은 것 붙이기! 이 세 박자면 어떤 리스트도 정렬할 수 있어요. 재귀랑 정렬을 한 번에 해냈으니 정말 잘했어요! 👏"

▸ 더 해보기 — 여기서부터는 선택!

여기까지가 오늘의 필수 내용이에요. 아래는 여유 있을 때 도전하는 내용이고, 예제 문제로 직접 풀어볼 수 있어요. 외울 필요는 없어요.

단계별 출력로 과정 보기 — merge_sort에 depth(깊이)를 넘기고 분할·합치기마다 print 하면, 위에서 본 분할→합치기 과정을 글자로 눈에 볼 수 있어요. → 예제로 연습
공통 원소 찾기 — merge에서 쓴 두 포인터는 합치기 말고도 써요. 정렬된 두 리스트에서 양쪽에 다 있는 수를 찾을 때, 두 값이 같을 때만 담으면 돼요. 골격은 같고 담는 조건만 달라요. → 예제로 연습
내림차순으로 합치기 — merge의 <= 를 >= 로 바꾸면 큰 수부터(내림차순) 정렬돼요. → 예제로 연습

🐬 돌핀쌤: "기본을 완벽히 익힌 다음 도전하세요. 변형은 전부 '반으로 나누기 + 두 포인터 합치기'라는 같은 뼈대 위에 살을 붙인 거예요."

참고 — 왜 O(n log n)일까?

log n번의 분할 단계 × 각 단계 n개 비교 = n log n을 보여주는 도식

병합 정렬은 리스트를 반으로 계속 나눠요. 8개를 1개가 될 때까지 나누면 8 → 4 → 2 → 1 로 3번이면 돼요. 이 "절반씩 나누는 횟수"를 log n 이라고 해요(log₂8 = 3).

그리고 한 단계에서 합칠 때 원소를 전부 한 번씩 보니까 n번 비교해요. 그래서 전체는 단계 수(log n) × 각 단계(n) = O(n log n) 이에요.

n	O(n²) 버블 정렬(8차시)	O(n log n) 병합 정렬	차이
100	10,000	약 664	약 15배
1,000	1,000,000	약 9,966	약 100배
10,000	100,000,000	약 132,877	약 750배

데이터가 많을수록 병합 정렬이 압도적으로 빨라요. 8차시 버블 정렬(O(n²))과 비교하면 차이가 확 벌어지죠. 그래서 데이터가 많을 땐 병합 정렬 같은 O(n log n) 정렬을 써요.

12 — (심화) 병합 정렬

📃 해결할 문제

💻 예제 입력 1

🖨️ 예제 출력 1