PostsSeriesLabsAlgo

정렬

병합 정렬

반으로 쪼갰다 붙이기

이미 정렬된 두 묶음을 하나의 줄로 합쳐 보세요. 카드는 한 장씩 새 줄로 내려갑니다.

카드 여섯 장이 두 묶음으로 서 있습니다. 두 묶음 모두 이미 작은 수부터 정렬돼 있습니다. 하나의 줄로 합치려면 카드를 몇 번 내려놓아야 할지 먼저 맞혀 보세요

왼쪽 묶음

오른쪽 묶음

새 줄 — 왼쪽이 가장 작게

여기에 한 장씩 내려놓습니다
내려놓은 횟수 0 · 틀리게 누른 횟수 0

카드 여섯 장을 0번 내려놓아 합쳤습니다. 맨 앞 두 장만 견주면 됐습니다. 견준 횟수는 0번입니다.

2 5 9 + 1 4 7 → 1 2 4 5 7 9맨 앞 두 장만 견주며 한 장씩 내려놓은 결과입니다.

이미 정렬된 두 묶음을 하나로 합치는 방법 = 병합(합치기)

정렬이 안 된 카드 여덟 장도 이걸로 정렬할 수 있습니다. 반으로 쪼개고 또 쪼개면 한 장씩이 됩니다. 한 장은 이미 정렬된 묶음이라 거꾸로 합쳐 올라가면 끝납니다.

6 3 8 1 7 2 5 41 2 3 4 5 6 7 86 3 8 11 3 6 87 2 5 42 4 5 76 33 68 11 87 22 75 44 563817254
위에서 아래로 쪼개고, 아래에서 위로 합칩니다. 묶음 아래의 색 숫자가 합쳐서 정렬한 모양입니다.

반으로 쪼갠 뒤 합치며 올라가는 방법 = 병합 정렬

쪼개기는 한 장에서 멈춘다

  • 두 묶음이 각각 정렬돼 있다 — 그래서 맨 앞 두 장만 견주면 됐다. ① 에서 뒤쪽 카드를 누를 수 없던 이유다
  • 한 장짜리 묶음은 이미 정렬돼 있다 — 쪼개기를 여기서 멈춘다. 재귀가 멈추는 자리와 같다
  • 층마다 — 합치며 카드를 한 번씩 내려놓는다. 반으로 쪼갠 횟수가 층 수다. 8장은 3층, 1000장은 10층이다

반으로 몇 번 쪼개면 1이 되는지가 log N 입니다. 층 수 × 카드 수가 곧 N log N 입니다.

버블 정렬 · 1000장499,500번
병합 정렬 · 1000장9,966번
같은 1000장을 정렬할 때 카드를 견주거나 내려놓는 횟수입니다. 1,000,000장이면 약 2천만 번 대 5천억 번입니다. 시간으로는 2초 대 14시간쯤입니다(Python 1초 ≈ 1천만 번 어림).

코드는 쪼개는 함수와 합치는 함수 둘이다

다음을 눌러 한 줄씩 넘기며 위 줄에서 묶음이 합쳐지고 아래 줄이 채워지는 걸 보세요. 재귀로 부르는 줄(5·6번)과 i += 1 같은 짧은 줄은 건너뜁니다. 마지막 합치기가 ① 에서 한 일입니다.

다음을 눌러 한 줄씩 넘겨 보세요

n = 6 mid = 3

merge_sort.py
  1. 1def merge_sort(arr):
  2. 2 if len(arr) <= 1:
  3. 3 return arr
  4. 4 mid = len(arr) // 2
  5. 5 left = merge_sort(arr[:mid])
  6. 6 right = merge_sort(arr[mid:])
  7. 7 return merge(left, right)
  8. 8
  9. 9def merge(left, right):
  10. 10 result = []
  11. 11 i = j = 0
  12. 12 while i < len(left) and j < len(right):
  13. 13 if left[i] <= right[j]:
  14. 14 result.append(left[i])
  15. 15 i += 1
  16. 16 else:
  17. 17 result.append(right[j])
  18. 18 j += 1
  19. 19 result += left[i:] + right[j:]
  20. 20 return result
0 / 40
  • merge_sort(arr) — 반으로 나눠 각각 정렬해 돌려받고 merge 로 합친다. 자기를 두 번 부르는 재귀다
  • left[i] <= right[j] — 두 묶음의 맨 앞 두 장 중 작은 쪽을 고른다. ① 에서 한 일이다
  • result — 합쳐서 만드는 줄. 위 그림의 아래 줄이다

이미 작은 수부터 서 있는 카드 8장을 병합 정렬하면 카드를 모두 몇 번 내려놓을까요?

병합 정렬에서 틀리는 자리

  • <= 대신 < — 같은 값에서 오른쪽 카드가 먼저 나와 원래 순서가 뒤집힌다. 2a 1c 2b 를 정렬하면 <= 는 1c 2a 2b, < 는 1c 2b 2a 순서가 된다
  • result += left[i:] + right[j:] 를 빼먹으면 — 한쪽 묶음이 먼저 비었을 때 남은 카드가 사라진다. 여섯 장 5 2 9 1 7 4 를 정렬하면 1장만 남는다
  • arr[:mid] 는 복사다 — 카드를 새 리스트로 옮기니 메모리를 카드 수만큼 더 쓴다. 쪼개는 깊이는 log N 이라 100만 장도 20층이다. RecursionError 는 걱정하지 않아도 된다

문제에서 이 말이 보이면

같은 값의 순서를 지켜야 한다N 이 커도 최악이 N log N정렬된 두 묶음을 합친다

실전에서 정렬이 필요하면 sorted() 한 줄이면 됩니다. 파이썬의 sorted() 는 병합 정렬과 삽입 정렬을 섞은 방법을 C 로 구현해 둬서 직접 만든 이 코드보다 훨씬 빠릅니다. Python 3.14 에서 10만 장을 재 보니 이 코드는 0.13초, sorted() 는 0.008초였습니다(컴퓨터마다 다르니 비율만 보세요).

다음 장에서는 기준 카드 하나로 좌우를 가르는 퀵 정렬을 봅니다.