본문 바로가기
알고리즘

O(n²)의 벽을 넘어서기 위한 관문, 병합 정렬

by Renechoi 2025. 7. 11.

 

버블, 삽입, 선택 정렬을 직관적인 알고리즘이다. 이 알고리즘들은 직관적이지만 데이터가 많아지면 속도에 한계가 있다.

 

오늘은 그 한계를 뛰어넘는 병합 정렬(Merge Sort)에 대해 이야기 나눠보고자 한다. 단순히 "병합 정렬은 빠르다"에서 그치지 않고, 우리가 배운 정렬들과 비교하며 "왜 빠른지", "어떤 대가를 치르는지" 함께 질문하고 답을 찾아가는 시간을 가져보자.

 

 

 

🚀 본격적인 탐구에 앞서: 접근법의 차이

버블, 삽입, 선택 정렬의 공통점은 바로 배열의 처음부터 끝까지 차근차근 훑어보면서 제자리를 찾아주는 방식이라는 것이다. 마치 책상 위 엉망인 책들을 한 권씩 순서대로 꽂아 넣는 것처럼 말이다.

 

그런데 오늘 배울 병합 정렬은 생각의 방향이 완전히 다르다.

 

질문 1: 버블, 삽입, 선택 정렬은 배열의 처음부터 끝까지 차근차근 훑어보는 방식이라면 병합 정렬의 '분할 정복(Divide and Conquer)'은 이와 어떻게 다를까?

 

분할 정복이란 말 그대로 '나누고(Divide) 정복한다(Conquer)'는 뜻이다. 병합 정렬은 어려운 문제를 잘게 쪼개서 쉬운 문제로 만든 다음, 그 쉬운 문제들을 해결하고 합치는 방식으로 동작한다.

 

예를 들어 책이 100권 있을 때, 한 번에 순서대로 꽂는 것과 10권씩 10묶음으로 나눈 뒤 각 묶음을 정렬하고 합치는 것 중 어떤 게 더 쉬울까? 후자가 훨씬 수월할 것이다. 병합 정렬도 같은 원리다.

 

<svg viewBox="0 0 800 600" xmlns="http://www.w3.org/2000/svg"> <!-- 배경 --> <rect width="800" height="600" fill="#f8f9fa"/> <!-- 제목 -->
<text x="400" y="30" text-anchor="middle" font-size="20" font-weight="bold" fill="#333">병합 정렬 과정</text>

<!-- Level 0 (원본 배열) --> <g id="level0"> <rect x="250" y="60" width="300" height="40" fill="#e3f2fd" stroke="#1976d2" stroke-width="2" rx="5"/> <text x="400" y="85" text-anchor="middle" font-size="16" fill="#333">[8, 3, 5, 1, 7, 2, 6, 4]</text> </g> <!-- 분할 단계 라벨 -->
<text x="100" y="130" font-size="14" font-weight="bold" fill="
#d32f2f">분할 (Divide) ↓</text>

<!-- Level 1 --> <g id="level1"> <rect x="150" y="140" width="140" height="35" fill="#fff3e0" stroke="#f57c00" stroke-width="2" rx="5"/> <text x="220" y="162" text-anchor="middle" font-size="14" fill="#333">[8, 3, 5, 1]</text>
<rect x="510" y="140" width="140" height="35" fill="#fff3e0" stroke="#f57c00" stroke-width="2" rx="5"/>
<text x="580" y="162" text-anchor="middle" font-size="14" fill="#333">[7, 2, 6, 4]</text>
</g> <!-- Level 2 --> <g id="level2"> <rect x="100" y="210" width="70" height="30" fill="#fce4ec" stroke="#c2185b" stroke-width="2" rx="5"/> <text x="135" y="230" text-anchor="middle" font-size="12" fill="#333">[8, 3]</text>
<rect x="220" y="210" width="70" height="30" fill="#fce4ec" stroke="#c2185b" stroke-width="2" rx="5"/>
<text x="255" y="230" text-anchor="middle" font-size="12" fill="#333">[5, 1]</text>

<rect x="460" y="210" width="70" height="30" fill="#fce4ec" stroke="#c2185b" stroke-width="2" rx="5"/>
<text x="495" y="230" text-anchor="middle" font-size="12" fill="#333">[7, 2]</text>

<rect x="580" y="210" width="70" height="30" fill="#fce4ec" stroke="#c2185b" stroke-width="2" rx="5"/>
<text x="615" y="230" text-anchor="middle" font-size="12" fill="#333">[6, 4]</text>
</g> <!-- Level 3 (개별 원소) --> <g id="level3"> <rect x="80" y="270" width="30" height="25" fill="#f3e5f5" stroke="#7b1fa2" stroke-width="2" rx="5"/> <text x="95" y="287" text-anchor="middle" font-size="12" fill="#333">[8]</text>
<rect x="130" y="270" width="30" height="25" fill="#f3e5f5" stroke="#7b1fa2" stroke-width="2" rx="5"/>
<text x="145" y="287" text-anchor="middle" font-size="12" fill="#333">[3]</text>

<rect x="200" y="270" width="30" height="25" fill="#f3e5f5" stroke="#7b1fa2" stroke-width="2" rx="5"/>
<text x="215" y="287" text-anchor="middle" font-size="12" fill="#333">[5]</text>

<rect x="250" y="270" width="30" height="25" fill="#f3e5f5" stroke="#7b1fa2" stroke-width="2" rx="5"/>
<text x="265" y="287" text-anchor="middle" font-size="12" fill="#333">[1]</text>

<rect x="440" y="270" width="30" height="25" fill="#f3e5f5" stroke="#7b1fa2" stroke-width="2" rx="5"/>
<text x="455" y="287" text-anchor="middle" font-size="12" fill="#333">[7]</text>

<rect x="490" y="270" width="30" height="25" fill="#f3e5f5" stroke="#7b1fa2" stroke-width="2" rx="5"/>
<text x="505" y="287" text-anchor="middle" font-size="12" fill="#333">[2]</text>

<rect x="560" y="270" width="30" height="25" fill="#f3e5f5" stroke="#7b1fa2" stroke-width="2" rx="5"/>
<text x="575" y="287" text-anchor="middle" font-size="12" fill="#333">[6]</text>

<rect x="610" y="270" width="30" height="25" fill="#f3e5f5" stroke="#7b1fa2" stroke-width="2" rx="5"/>
<text x="625" y="287" text-anchor="middle" font-size="12" fill="#333">[4]</text>
</g> <!-- 병합 단계 라벨 -->
<text x="100" y="320" font-size="14" font-weight="bold" fill="
#388e3c">병합 (Merge) ↑</text>

<!-- Level 4 (첫 번째 병합) --> <g id="level4"> <rect x="100" y="340" width="70" height="30" fill="#e8f5e9" stroke="#388e3c" stroke-width="2" rx="5"/> <text x="135" y="360" text-anchor="middle" font-size="12" fill="#333">[3, 8]</text>
<rect x="220" y="340" width="70" height="30" fill="#e8f5e9" stroke="#388e3c" stroke-width="2" rx="5"/>
<text x="255" y="360" text-anchor="middle" font-size="12" fill="#333">[1, 5]</text>

<rect x="460" y="340" width="70" height="30" fill="#e8f5e9" stroke="#388e3c" stroke-width="2" rx="5"/>
<text x="495" y="360" text-anchor="middle" font-size="12" fill="#333">[2, 7]</text>

<rect x="580" y="340" width="70" height="30" fill="#e8f5e9" stroke="#388e3c" stroke-width="2" rx="5"/>
<text x="615" y="360" text-anchor="middle" font-size="12" fill="#333">[4, 6]</text>
</g> <!-- Level 5 --> <g id="level5"> <rect x="150" y="400" width="140" height="35" fill="#c8e6c9" stroke="#2e7d32" stroke-width="2" rx="5"/> <text x="220" y="422" text-anchor="middle" font-size="14" fill="#333">[1, 3, 5, 8]</text>
<rect x="510" y="400" width="140" height="35" fill="#c8e6c9" stroke="#2e7d32" stroke-width="2" rx="5"/>
<text x="580" y="422" text-anchor="middle" font-size="14" fill="#333">[2, 4, 6, 7]</text>
</g> <!-- Level 6 (최종 결과) --> <g id="level6"> <rect x="250" y="470" width="300" height="40" fill="#4caf50" stroke="#1b5e20" stroke-width="3" rx="5"/> <text x="400" y="495" text-anchor="middle" font-size="16" font-weight="bold" fill="#fff">[1, 2, 3, 4, 5, 6, 7, 8]</text> <text x="400" y="530" text-anchor="middle" font-size="14" font-weight="bold" fill="#4caf50">정렬 완료!</text> </g> <!-- 화살표들 --> <defs> <marker id="arrowhead" markerWidth="10" markerHeight="7" refX="9" refY="3.5" orient="auto"> <polygon points="0 0, 10 3.5, 0 7" fill="#666"/> </marker> </defs> <!-- 분할 화살표 --> <line x1="350" y1="100" x2="250" y2="140" stroke="#666" stroke-width="2" marker-end="url(#arrowhead)"/> <line x1="450" y1="100" x2="550" y2="140" stroke="#666" stroke-width="2" marker-end="url(#arrowhead)"/> <line x1="200" y1="175" x2="150" y2="210" stroke="#666" stroke-width="1.5" marker-end="url(#arrowhead)"/> <line x1="240" y1="175" x2="260" y2="210" stroke="#666" stroke-width="1.5" marker-end="url(#arrowhead)"/> <line x1="560" y1="175" x2="510" y2="210" stroke="#666" stroke-width="1.5" marker-end="url(#arrowhead)"/> <line x1="600" y1="175" x2="620" y2="210" stroke="#666" stroke-width="1.5" marker-end="url(#arrowhead)"/> <!-- 병합 화살표 --> <line x1="135" y1="295" x2="135" y2="340" stroke="#388e3c" stroke-width="2" marker-end="url(#arrowhead)"/> <line x1="255" y1="295" x2="255" y2="340" stroke="#388e3c" stroke-width="2" marker-end="url(#arrowhead)"/> <line x1="495" y1="295" x2="495" y2="340" stroke="#388e3c" stroke-width="2" marker-end="url(#arrowhead)"/> <line x1="615" y1="295" x2="615" y2="340" stroke="#388e3c" stroke-width="2" marker-end="url(#arrowhead)"/> <line x1="200" y1="370" x2="200" y2="400" stroke="#388e3c" stroke-width="2" marker-end="url(#arrowhead)"/> <line x1="540" y1="370" x2="540" y2="400" stroke="#388e3c" stroke-width="2" marker-end="url(#arrowhead)"/> <line x1="300" y1="435" x2="350" y2="470" stroke="#388e3c" stroke-width="2.5" marker-end="url(#arrowhead)"/> <line x1="500" y1="435" x2="450" y2="470" stroke="#388e3c" stroke-width="2.5" marker-end="url(#arrowhead)"/> </svg>

 

 

 

이 그림은 병합 정렬의 두 가지 핵심 단계를 보여준다.

 

분할 (Divide) - (위에서 아래로 🔽)

원본 배열 [8, 3, 5, 1, 7, 2, 6, 4]가 더 이상 쪼갤 수 없을 때까지(크기가 1이 될 때까지) 계속해서 절반으로 나뉜다. 이 단계에서는 실제 정렬이 일어나지 않고, 문제를 잘게 나누기만 한다.

 

정복 (Conquer / Merge) - (아래에서 위로 🔼)

크기가 1인 배열들부터 시작해서, 두 개의 정렬된 부분 배열을 합쳐 하나의 더 큰 정렬된 배열로 만든다. 예를 들어, [3]과 [8]을 합쳐 [3, 8]을 만들고, [1]과 [5]를 합쳐 [1, 5]를 만든다. 이 병합 과정을 재귀적으로 반복하면 최종적으로 완벽하게 정렬된 배열을 얻게 된다.

 

이전에 배웠던 방식과는 문제에 접근하는 방식 자체가 다르다는 게 느껴질 것이다.

🤔 성능에 대한 고찰: 시간과 공간의 트레이드오프

병합 정렬이 문제를 잘게 쪼개서 해결한다는 것을 봤다. 이 똑똑한 접근 방식은 성능에 어마어마한 영향을 준다.

 

질문 2: 병합 정렬의 시간 복잡도는 O(n log n)이다. 우리가 배운 O(n²) 정렬들과 비교하면 얼마나, 그리고 왜 더 효율적일까?

 

O(n²)와 O(n log n), 그냥 보면 큰 차이가 아닌 것 같다. 하지만 데이터가 많아지면 이야기가 완전히 달라진다.

 

<svg viewBox="0 0 800 500" xmlns="http://www.w3.org/2000/svg"> <!-- 배경 --> <rect width="800" height="500" fill="#f5f5f5"/> <!-- 제목 -->
<text x="400" y="30" text-anchor="middle" font-size="22" font-weight="bold" fill="#333">시간 복잡도 비교: O(n²) vs O(n log n)</text>

<!-- 데이터 크기 1,000개 섹션 --> <g id="section1000"> <rect x="50" y="60" width="700" height="180" fill="#fff" stroke="#ddd" stroke-width="1" rx="5"/> <text x="70" y="90" font-size="18" font-weight="bold" fill="#333">데이터 크기: 1,000개</text>
<!-- O(n²) 막대 -->
<text x="70" y="120" font-size="14" fill="#666">O(n²) 알고리즘:</text>
<rect x="200" y="105" width="480" height="25" fill="#ff5252" rx="3"/>
<text x="690" y="122" font-size="14" fill="#333">1,000,000번 (백만 번)</text>

<!-- O(n log n) 막대 -->
<text x="70" y="160" font-size="14" fill="#666">O(n log n) 알고리즘:</text>
<rect x="200" y="145" width="48" height="25" fill="#4caf50" rx="3"/>
<text x="258" y="162" font-size="14" fill="#333">10,000번 (만 번)</text>

<!-- 비교 -->
<rect x="70" y="190" width="120" height="35" fill="#fff3e0" stroke="#ff9800" stroke-width="2" rx="5"/>
<text x="130" y="213" text-anchor="middle" font-size="16" font-weight="bold" fill="#ff6f00">100배 차이!</text>
</g> <!-- 데이터 크기 1,000,000개 섹션 --> <g id="section1000000"> <rect x="50" y="260" width="700" height="180" fill="#fff" stroke="#ddd" stroke-width="1" rx="5"/> <text x="70" y="290" font-size="18" font-weight="bold" fill="#333">데이터 크기: 1,000,000개 (백만 개)</text>
<!-- O(n²) 막대 -->
<text x="70" y="320" font-size="14" fill="#666">O(n²) 알고리즘:</text>
<rect x="200" y="305" width="480" height="25" fill="#d32f2f" rx="3"/>
<rect x="200" y="335" width="480" height="25" fill="#d32f2f" rx="3"/>
<text x="690" y="322" font-size="14" fill="#333">1조 번 🤯</text>
<text x="200" y="380" font-size="12" fill="#666">(화면에 다 표시할 수 없을 정도로 많음)</text>

<!-- O(n log n) 막대 -->
<text x="70" y="410" font-size="14" fill="#666">O(n log n) 알고리즘:</text>
<rect x="200" y="395" width="15" height="25" fill="#2e7d32" rx="3"/>
<text x="225" y="412" font-size="14" fill="#333">20,000,000번 (2천만 번)</text>
</g> <!-- 비교 강조 --> <rect x="250" y="450" width="300" height="40" fill="#ffebee" stroke="#f44336" stroke-width="3" rx="5"/> <text x="400" y="475" text-anchor="middle" font-size="20" font-weight="bold" fill="#c62828">50,000배 차이! 🚀</text> <!-- 범례 --> <g id="legend"> <rect x="600" y="70" width="15" height="15" fill="#ff5252"/> <text x="620" y="82" font-size="12" fill="#666">O(n²)</text>
<rect x="600" y="90" width="15" height="15" fill="#4caf50"/>
<text x="620" y="102" font-size="12" fill="#666">O(n log n)</text>
</g> </svg>

 

 

데이터가 1,000개일 때:

  • O(n²) ≈ 1,000 × 1,000 = 1,000,000 (백만) 번 연산
  • O(n log₂n) ≈ 1,000 × 10 = 10,000 (만) 번 연산

데이터가 1,000,000개(백만 개)일 때:

  • O(n²) ≈ 10⁶ × 10⁶ = 1,000,000,000,000 (1조) 번 연산
  • O(n log₂n) ≈ 10⁶ × 20 = 20,000,000 (2천만) 번 연산

데이터가 커질수록 O(n²)는 거의 재앙에 가깝지만, O(n log n)은 매우 안정적으로 증가한다. 이것이 코딩 테스트에서 N의 범위가 클 때 O(n²) 풀이가 시간 초과로 실패하고, O(n log n) 풀이가 통과하는 이유다.

 

삽입 정렬은 데이터가 거의 정렬된 상태일 때 O(n)까지 빨라졌던 것과 달리, 병합 정렬은 데이터의 초기 상태와 상관없이 언제나 꾸준하게 O(n log n)의 성능을 보여준다. 이런 예측 가능성은 매우 큰 장점이다.

 

그렇다면 O(n log n)은 어떻게 나오는 걸까?

 

 

병합 정렬의 시간 복잡도를 이해하려면 두 가지 핵심을 파악해야 한다.

 

1. 분할 단계: 몇 번이나 반으로 나눌 수 있을까?

8개의 데이터를 생각해보자:

  • 1번째 분할: 8 → 4, 4
  • 2번째 분할: 4, 4 → 2, 2, 2, 2
  • 3번째 분할: 2, 2, 2, 2 → 1, 1, 1, 1, 1, 1, 1, 1

8 = 2³이므로 3번 분할했다. 일반적으로 n개의 데이터는 log₂n번 분할할 수 있다.

 

왜 log₂n일까? n을 계속 2로 나누어 1이 될 때까지의 횟수가 바로 log₂n이기 때문이다.

  • n = 8일 때: log₂8 = 3
  • n = 1024일 때: log₂1024 = 10
  • n = 1,000,000일 때: log₂1,000,000 ≈ 20

2. 병합 단계: 각 레벨에서 얼마나 많은 비교를 할까?

 

이제 병합 과정을 자세히 보자. 슈도코드로 표현하면:

두 개의 정렬된 배열 A와 B를 병합하는 과정:
1. A의 첫 번째 원소와 B의 첫 번째 원소를 비교
2. 더 작은 것을 결과 배열에 추가
3. 추가한 쪽의 다음 원소로 이동
4. 둘 중 하나가 끝날 때까지 반복
5. 남은 원소들을 모두 결과 배열에 추가

 

예를 들어 [3, 8]과 [1, 5]를 병합한다면:

  • 3과 1 비교 → 1 선택
  • 3과 5 비교 → 3 선택
  • 8과 5 비교 → 5 선택
  • 8이 남음 → 8 추가

중요한 점은 각 레벨에서 모든 n개의 원소가 정확히 한 번씩 비교되거나 이동한다는 것이다.

 

<svg viewBox="0 0 600 400" xmlns="http://www.w3.org/2000/svg"> <rect width="600" height="400" fill="#f8f9fa"/>
<text x="300" y="30" text-anchor="middle" font-size="18" font-weight="bold">각 레벨에서의 작업량</text>

<!-- Level indicators -->
<text x="50" y="80" font-size="14" fill="#666">레벨 0:</text> <text x="50" y="140" font-size="14" fill="#666">레벨 1:</text> <text x="50" y="200" font-size="14" fill="#666">레벨 2:</text> <text x="50" y="260" font-size="14" fill="#666">레벨 3:</text>

<!-- Level 0 --> <rect x="120" y="60" width="400" height="30" fill="#e3f2fd" stroke="#1976d2"/> <text x="320" y="80" text-anchor="middle" font-size="12">8개 원소 (1개 그룹)</text> <!-- Level 1 --> <rect x="120" y="120" width="195" height="30" fill="#fff3e0" stroke="#f57c00"/> <rect x="325" y="120" width="195" height="30" fill="#fff3e0" stroke="#f57c00"/> <text x="217" y="140" text-anchor="middle" font-size="12">4개</text> <text x="422" y="140" text-anchor="middle" font-size="12">4개</text> <!-- Level 2 --> <rect x="120" y="180" width="92" height="30" fill="#fce4ec" stroke="#c2185b"/> <rect x="222" y="180" width="93" height="30" fill="#fce4ec" stroke="#c2185b"/> <rect x="325" y="180" width="92" height="30" fill="#fce4ec" stroke="#c2185b"/> <rect x="427" y="180" width="93" height="30" fill="#fce4ec" stroke="#c2185b"/> <text x="166" y="200" text-anchor="middle" font-size="12">2개</text> <text x="268" y="200" text-anchor="middle" font-size="12">2개</text> <text x="371" y="200" text-anchor="middle" font-size="12">2개</text> <text x="473" y="200" text-anchor="middle" font-size="12">2개</text> <!-- Level 3 --> <g font-size="12"> <rect x="120" y="240" width="40" height="30" fill="#f3e5f5" stroke="#7b1fa2"/> <rect x="170" y="240" width="40" height="30" fill="#f3e5f5" stroke="#7b1fa2"/> <rect x="220" y="240" width="40" height="30" fill="#f3e5f5" stroke="#7b1fa2"/> <rect x="270" y="240" width="40" height="30" fill="#f3e5f5" stroke="#7b1fa2"/> <rect x="320" y="240" width="40" height="30" fill="#f3e5f5" stroke="#7b1fa2"/> <rect x="370" y="240" width="40" height="30" fill="#f3e5f5" stroke="#7b1fa2"/> <rect x="420" y="240" width="40" height="30" fill="#f3e5f5" stroke="#7b1fa2"/> <rect x="470" y="240" width="40" height="30" fill="#f3e5f5" stroke="#7b1fa2"/> <text x="140" y="260" text-anchor="middle">1</text> <text x="190" y="260" text-anchor="middle">1</text> <text x="240" y="260" text-anchor="middle">1</text> <text x="290" y="260" text-anchor="middle">1</text> <text x="340" y="260" text-anchor="middle">1</text> <text x="390" y="260" text-anchor="middle">1</text> <text x="440" y="260" text-anchor="middle">1</text> <text x="490" y="260" text-anchor="middle">1</text> </g> <!-- Work per level -->
<text x="540" y="80" font-size="14" font-weight="bold" fill="
#1976d2">= n</text> <text x="540" y="140" font-size="14" font-weight="bold" fill="
#f57c00">= n</text> <text x="540" y="200" font-size="14" font-weight="bold" fill="
#c2185b">= n</text> <text x="540" y="260" font-size="14" font-weight="bold" fill="
#7b1fa2">= n</text>

<rect x="50" y="310" width="500" height="60" fill="#e8f5e9" stroke="#388e3c" stroke-width="2" rx="5"/> <text x="300" y="340" text-anchor="middle" font-size="16" font-weight="bold" fill="#2e7d32"> 총 작업량 = 레벨 수 × 레벨당 작업량 = log₂n × n = n log n </text> </svg>

 

 

최종 정리:

  • 전체 레벨 수: log₂n개 (계속 반으로 나누기 때문)
  • 각 레벨에서의 작업량: n개 (모든 원소가 한 번씩 처리됨)
  • 총 시간 복잡도: O(n × log₂n) = O(n log n)

이것이 병합 정렬이 데이터의 초기 상태와 무관하게 항상 O(n log n)의 성능을 보이는 이유다. 데이터가 이미 정렬되어 있든, 역순이든, 무작위든 상관없이 정확히 log n개의 레벨을 거쳐야 하고, 각 레벨에서 n개의 원소를 처리해야 한다.

 

하지만 세상에 공짜는 없다.

 

질문 3: 이 엄청난 속도는 어떤 대가를 치를까? 우리가 배운 정렬들과의 가장 큰 차이점은 무엇일까?

 

정답은 바로 '메모리 사용량'이다.

 

병합 과정에서 두 개의 정렬된 부분을 합쳐서 새로운 배열을 만들 때, 정렬할 배열과 똑같은 크기의 추가적인 메모리 공간(O(n))이 필요하다.

 

버블, 삽입, 선택 정렬은 주어진 배열 안에서 값의 위치만 바꾸는 '제자리 정렬(In-place Sort)'이라 추가 메모리가 거의 필요 없었다(O(1)). 하지만 병합 정렬은 추가 메모리를 사용하는 '외부 정렬(Out-of-place Sort)*이다.

 

메모리를 더 쓴다는 건 분명한 단점이다. 그럼에도 불구하고 병합 정렬을 배워야 하는 이유는 그 단점을 상쇄하고도 남을 만큼 '속도'와 '안정성'이라는 확실한 장점이 있기 때문이다.


✨ 실용적인 관점: 안정적인 정렬의 가치

병합 정렬의 또 다른 강력한 무기이자, 실무에서 정말 중요한 특징을 알아보자.

 

질문 4: 병합 정렬의 중요한 특징 중 하나는 '안정 정렬(Stable Sort)'이라는 점이다. 이게 왜 실무에서 중요할까?

 

'안정 정렬'이란 "중복된 값들의 기존 순서를 그대로 유지해주는 정렬"이다.

 

예를 들어, (5점, A학생), (3점, B학생), (5점, C학생)이라는 데이터가 있을 때, 점수 순으로 정렬한다고 해보자.

  • 안정 정렬(Stable) 결과: (3점, B학생), (5점, A학생), (5점, C학생) → 점수가 같은 A학생과 C학생의 원래 순서가 유지된다.
  • 불안정 정렬(Unstable) 결과: (3점, B학생), (5점, C학생), (5점, A학생) → 점수가 같은 A, C학생의 순서가 바뀔 수 있다.

우리가 배운 정렬 중에는:

  • 안정 정렬: 삽입 정렬, 버블 정렬
  • 불안정 정렬: 선택 정렬

이 '안정성'이 백엔드 개발자에게 중요한 이유를 실제 예시로 살펴보자.

 

회원 관리 페이지를 만든다고 하자. 사용자를 가입일 순으로 정렬하는 기능이 필요하다. 그런데 요구사항이 추가됐다. "가입일이 같으면, 이름의 가나다순으로 보여주세요."

 

불안정 정렬을 사용한다면:

  1. 먼저 모든 사용자를 '이름' 순으로 정렬한다.
  2. 그다음, 이 결과를 다시 '가입일' 순으로 정렬한다.
  3. 이때 정렬 알고리즘이 불안정하다면, 같은 날 가입한 사용자들의 순서가 뒤섞여 버린다.

안정 정렬인 병합 정렬을 사용하면, 가입일이 같은 회원들의 기존 순서(이미 정렬된 이름 순)를 그대로 유지해준다. 덕분에 여러 조건으로 데이터를 정렬해야 할 때 아주 깔끔하게 문제를 해결할 수 있다.


💻 병합 정렬의 구현: 자연어로 이해하기

이제 병합 정렬이 실제로 어떻게 동작하는지 자연어 수준의 슈도코드로 살펴보자. 복잡해 보일 수 있지만, 두 가지 핵심 함수만 이해하면 된다.

1. 메인 함수: MergeSort (분할 담당)

MergeSort(배열, 시작위치, 끝위치):
    만약 시작위치가 끝위치보다 작다면:  // 원소가 2개 이상일 때만
        중간위치 = (시작위치 + 끝위치) / 2
        
        // 왼쪽 절반 정렬
        MergeSort(배열, 시작위치, 중간위치)
        
        // 오른쪽 절반 정렬  
        MergeSort(배열, 중간위치+1, 끝위치)
        
        // 정렬된 두 부분을 병합
        Merge(배열, 시작위치, 중간위치, 끝위치)

이 함수는 재귀적으로 배열을 계속 반으로 나눈다. 더 이상 나눌 수 없을 때(원소가 1개일 때)까지 나눈 후, 다시 합치면서 올라온다.

2. 병합 함수: Merge (정복 담당)

Merge(배열, 시작, 중간, 끝):
    // 임시 배열 생성
    왼쪽배열 = 배열[시작...중간]의 복사본
    오른쪽배열 = 배열[중간+1...끝]의 복사본
    
    // 비교하며 병합
    i = 0  // 왼쪽배열 인덱스
    j = 0  // 오른쪽배열 인덱스
    k = 시작  // 원본배열 인덱스
    
    왼쪽배열과 오른쪽배열 모두에 원소가 남아있는 동안:
        만약 왼쪽배열[i] ≤ 오른쪽배열[j]라면:
            배열[k] = 왼쪽배열[i]
            i를 1 증가
        아니라면:
            배열[k] = 오른쪽배열[j]
            j를 1 증가
        k를 1 증가
    
    // 남은 원소들 처리
    왼쪽배열에 남은 원소가 있다면:
        모두 배열[k...]에 복사
    
    오른쪽배열에 남은 원소가 있다면:
        모두 배열[k...]에 복사

 

실제 동작 예시

[3, 8, 1, 5]를 정렬한다고 해보자:

MergeSort([3, 8, 1, 5], 0, 3) 호출
│
├─ 중간 = 1
├─ MergeSort([3, 8, 1, 5], 0, 1) 호출  // 왼쪽 [3, 8]
│  ├─ 중간 = 0
│  ├─ MergeSort([3, 8, 1, 5], 0, 0)  // [3]
│  ├─ MergeSort([3, 8, 1, 5], 1, 1)  // [8]
│  └─ Merge([3, 8], 0, 0, 1) → [3, 8]  // 변화 없음
│
├─ MergeSort([3, 8, 1, 5], 2, 3) 호출  // 오른쪽 [1, 5]
│  ├─ 중간 = 2
│  ├─ MergeSort([3, 8, 1, 5], 2, 2)  // [1]
│  ├─ MergeSort([3, 8, 1, 5], 3, 3)  // [5]
│  └─ Merge([1, 5], 2, 2, 3) → [1, 5]  // 변화 없음
│
└─ Merge([3, 8, 1, 5], 0, 1, 3) 최종 병합
   왼쪽 = [3, 8], 오른쪽 = [1, 5]
   1 < 3 → [1, _, _, _]
   3 < 5 → [1, 3, _, _]
   5 < 8 → [1, 3, 5, _]
   8 남음 → [1, 3, 5, 8]

구현의 핵심 포인트

  1. 재귀의 아름다움: MergeSort 함수는 자기 자신을 호출하며 문제를 작게 만든다. 원소가 1개일 때는 이미 정렬된 것이므로 아무것도 하지 않는다.
  2. 병합의 효율성: 이미 정렬된 두 배열을 합치는 것은 매우 효율적이다. 각 원소를 한 번씩만 비교하면 된다.
  3. 안정성의 비밀: Merge 함수에서 왼쪽배열[i] ≤ 오른쪽배열[j] 조건에 주목하자. 같을 때(=) 왼쪽 것을 먼저 선택하므로 원래 순서가 유지된다.
  4. 추가 메모리 사용: Merge 함수에서 임시 배열을 만드는 부분이 O(n) 추가 메모리가 필요한 이유다.

 

MergeSort에서 핵심은 아무래도 합치는 부분의 로직이다. 따라서 이 부분을 좀 더 자세히 살펴보자.

 

<svg viewBox="0 0 800 600" xmlns="http://www.w3.org/2000/svg"> <rect width="800" height="600" fill="#f9f9f9"/> <!-- 제목 -->
<text x="400" y="30" text-anchor="middle" font-size="20" font-weight="bold" fill="#333">병합(Merge) 과정 단계별 시각화</text> <text x="400" y="55" text-anchor="middle" font-size="14" fill="#666">[3, 8]과 [1, 5]를 병합하는 과정</text>

<!-- 초기 상태 --> <g id="initial-state"> <text x="50" y="100" font-size="16" font-weight="bold" fill="#333">초기 상태</text>
<!-- 왼쪽 배열 -->
<text x="50" y="130" font-size="14" fill="#666">왼쪽 배열:</text>
<rect x="150" y="110" width="40" height="30" fill="#e3f2fd" stroke="#1976d2" stroke-width="2"/>
<text x="170" y="130" text-anchor="middle" font-size="14">3</text>
<rect x="195" y="110" width="40" height="30" fill="#e3f2fd" stroke="#1976d2" stroke-width="2"/>
<text x="215" y="130" text-anchor="middle" font-size="14">8</text>

<!-- 오른쪽 배열 -->
<text x="300" y="130" font-size="14" fill="#666">오른쪽 배열:</text>
<rect x="400" y="110" width="40" height="30" fill="#fff3e0" stroke="#f57c00" stroke-width="2"/>
<text x="420" y="130" text-anchor="middle" font-size="14">1</text>
<rect x="445" y="110" width="40" height="30" fill="#fff3e0" stroke="#f57c00" stroke-width="2"/>
<text x="465" y="130" text-anchor="middle" font-size="14">5</text>

<!-- 결과 배열 -->
<text x="550" y="130" font-size="14" fill="#666">결과 배열:</text>
<rect x="640" y="110" width="40" height="30" fill="#f5f5f5" stroke="#999" stroke-width="1" stroke-dasharray="3,3"/>
<rect x="685" y="110" width="40" height="30" fill="#f5f5f5" stroke="#999" stroke-width="1" stroke-dasharray="3,3"/>
<rect x="730" y="110" width="40" height="30" fill="#f5f5f5" stroke="#999" stroke-width="1" stroke-dasharray="3,3"/>
<rect x="775" y="110" width="40" height="30" fill="#f5f5f5" stroke="#999" stroke-width="1" stroke-dasharray="3,3"/>

<!-- 포인터 -->

<text x="170" y="90" text-anchor="middle" font-size="12" fill="#d32f2f">i=0</text>

<text x="420" y="90" text-anchor="middle" font-size="12" fill="#d32f2f">j=0</text>
</g> <!-- Step 1 --> <g id="step1"> <text x="50" y="190" font-size="16" font-weight="bold" fill="#333">Step 1: 3과 1 비교</text> <text x="50" y="210" font-size="14" fill="#666">1 < 3 이므로 1을 선택</text>
<!-- 비교 시각화 -->
<rect x="150" y="230" width="40" height="30" fill="#e3f2fd" stroke="#1976d2" stroke-width="2"/>
<text x="170" y="250" text-anchor="middle" font-size="14">3</text>
<text x="270" y="250" text-anchor="middle" font-size="20" fill="#666">vs</text>
<rect x="350" y="230" width="40" height="30" fill="#fff3e0" stroke="#f57c00" stroke-width="3"/>
<text x="370" y="250" text-anchor="middle" font-size="14" font-weight="bold">1</text>
<text x="410" y="250" font-size="16" fill="#4caf50">✓</text>

<!-- 결과 -->
<text x="500" y="250" font-size="14" fill="#666">→</text>
<rect x="540" y="230" width="40" height="30" fill="#c8e6c9" stroke="#388e3c" stroke-width="2"/>
<text x="560" y="250" text-anchor="middle" font-size="14">1</text>
<rect x="585" y="230" width="40" height="30" fill="#f5f5f5" stroke="#999" stroke-width="1" stroke-dasharray="3,3"/>
<rect x="630" y="230" width="40" height="30" fill="#f5f5f5" stroke="#999" stroke-width="1" stroke-dasharray="3,3"/>
<rect x="675" y="230" width="40" height="30" fill="#f5f5f5" stroke="#999" stroke-width="1" stroke-dasharray="3,3"/>
</g> <!-- Step 2 --> <g id="step2"> <text x="50" y="300" font-size="16" font-weight="bold" fill="#333">Step 2: 3과 5 비교</text> <text x="50" y="320" font-size="14" fill="#666">3 < 5 이므로 3을 선택</text>
<!-- 비교 시각화 -->
<rect x="150" y="340" width="40" height="30" fill="#e3f2fd" stroke="#1976d2" stroke-width="3"/>
<text x="170" y="360" text-anchor="middle" font-size="14" font-weight="bold">3</text>
<text x="210" y="360" font-size="16" fill="#4caf50">✓</text>
<text x="270" y="360" text-anchor="middle" font-size="20" fill="#666">vs</text>
<rect x="350" y="340" width="40" height="30" fill="#fff3e0" stroke="#f57c00" stroke-width="2"/>
<text x="370" y="360" text-anchor="middle" font-size="14">5</text>

<!-- 결과 -->
<text x="500" y="360" font-size="14" fill="#666">→</text>
<rect x="540" y="340" width="40" height="30" fill="#c8e6c9" stroke="#388e3c" stroke-width="2"/>
<text x="560" y="360" text-anchor="middle" font-size="14">1</text>
<rect x="585" y="340" width="40" height="30" fill="#c8e6c9" stroke="#388e3c" stroke-width="2"/>
<text x="605" y="360" text-anchor="middle" font-size="14">3</text>
<rect x="630" y="340" width="40" height="30" fill="#f5f5f5" stroke="#999" stroke-width="1" stroke-dasharray="3,3"/>
<rect x="675" y="340" width="40" height="30" fill="#f5f5f5" stroke="#999" stroke-width="1" stroke-dasharray="3,3"/>
</g> <!-- Step 3 --> <g id="step3"> <text x="50" y="410" font-size="16" font-weight="bold" fill="#333">Step 3: 8과 5 비교</text> <text x="50" y="430" font-size="14" fill="#666">5 < 8 이므로 5를 선택</text>
<!-- 비교 시각화 -->
<rect x="150" y="450" width="40" height="30" fill="#e3f2fd" stroke="#1976d2" stroke-width="2"/>
<text x="170" y="470" text-anchor="middle" font-size="14">8</text>
<text x="270" y="470" text-anchor="middle" font-size="20" fill="#666">vs</text>
<rect x="350" y="450" width="40" height="30" fill="#fff3e0" stroke="#f57c00" stroke-width="3"/>
<text x="370" y="470" text-anchor="middle" font-size="14" font-weight="bold">5</text>
<text x="410" y="470" font-size="16" fill="#4caf50">✓</text>

<!-- 결과 -->
<text x="500" y="470" font-size="14" fill="#666">→</text>
<rect x="540" y="450" width="40" height="30" fill="#c8e6c9" stroke="#388e3c" stroke-width="2"/>
<text x="560" y="470" text-anchor="middle" font-size="14">1</text>
<rect x="585" y="450" width="40" height="30" fill="#c8e6c9" stroke="#388e3c" stroke-width="2"/>
<text x="605" y="470" text-anchor="middle" font-size="14">3</text>
<rect x="630" y="450" width="40" height="30" fill="#c8e6c9" stroke="#388e3c" stroke-width="2"/>
<text x="650" y="470" text-anchor="middle" font-size="14">5</text>
<rect x="675" y="450" width="40" height="30" fill="#f5f5f5" stroke="#999" stroke-width="1" stroke-dasharray="3,3"/>
</g> <!-- Step 4 --> <g id="step4"> <text x="50" y="520" font-size="16" font-weight="bold" fill="#333">Step 4: 남은 원소 처리</text> <text x="50" y="540" font-size="14" fill="#666">오른쪽 배열이 끝났으므로 왼쪽의 8을 추가</text>
<!-- 최종 결과 -->
<rect x="300" y="550" width="40" height="30" fill="#4caf50" stroke="#1b5e20" stroke-width="2"/>
<text x="320" y="570" text-anchor="middle" font-size="14" fill="#fff">1</text>
<rect x="345" y="550" width="40" height="30" fill="#4caf50" stroke="#1b5e20" stroke-width="2"/>
<text x="365" y="570" text-anchor="middle" font-size="14" fill="#fff">3</text>
<rect x="390" y="550" width="40" height="30" fill="#4caf50" stroke="#1b5e20" stroke-width="2"/>
<text x="410" y="570" text-anchor="middle" font-size="14" fill="#fff">5</text>
<rect x="435" y="550" width="40" height="30" fill="#4caf50" stroke="#1b5e20" stroke-width="2"/>
<text x="455" y="570" text-anchor="middle" font-size="14" fill="#fff">8</text>

<text x="500" y="570" font-size="14" font-weight="bold" fill="#4caf50">정렬 완료!</text>
</g> <!-- 화살표 마커 정의 --> <defs> <marker id="arrowhead-red" markerWidth="10" markerHeight="7" refX="0" refY="3.5" orient="auto"> <polygon points="0 0, 10 3.5, 0 7" fill="#d32f2f"/> </marker> </defs> </svg>

 

 

병합 과정의 핵심은 두 포인터를 이용한 비교다. 각 단계에서

  1. 두 배열의 현재 위치 원소를 비교한다
  2. 더 작은 값을 결과 배열에 넣는다
  3. 선택된 배열의 포인터를 한 칸 전진시킨다
  4. 한쪽 배열이 끝날 때까지 반복한다
  5. 남은 원소들을 그대로 복사한다

이 과정이 효율적인 이유는 이미 정렬된 배열을 다루기 때문이다. 각 원소는 정확히 한 번만 비교되고 한 번만 이동한다. 따라서 병합의 시간 복잡도는 O(n)이다.

 

특히 주목할 점은 Step 2에서 만약 왼쪽과 오른쪽 값이 같았다면(예: 둘 다 3), 왼쪽 것을 먼저 선택한다는 것이다. 이것이 병합 정렬이 안정 정렬인 이유다.


이렇게 단순한 분할과 병합의 반복으로 O(n log n)의 효율적인 정렬이 완성된다. 복잡해 보이지만, "나누고 → 정렬하고 → 합친다"는 핵심 아이디어만 기억하면 된다.





🎬 마무리: 오늘 우리가 가져갈 것들

핵심 정리

  1. 병합 정렬은 분할 정복에 기반하여 O(n²)의 한계를 극복하는 효율적인 알고리즘이다.
  2. 최선, 평균, 최악 모두 O(n log n) 시간 복잡도를 보장하여 예측 가능한 성능을 제공한다.
  3. O(n)의 추가 공간을 사용하는 대신, 속도와 **안정성(Stability)**이라는 두 마리 토끼를 잡았다.
  4. 실무에서는 단순히 빠른 것뿐만 아니라, 다중 조건 정렬 등에서 데이터의 정렬 안정성이 중요한 고려사항이 될 수 있다.

병합 정렬은 단순히 "빠른 정렬"이 아니라, 컴퓨터 과학의 핵심 개념인 분할 정복을 이해하고, 시간과 공간의 트레이드오프를 고민하며, 실무적 요구사항을 만족시키는 균형 잡힌 알고리즘이다.

 

 

 

 

 

 

 

 

 

반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘' 카테고리의 다른 글

O(n²) 너머 ②: 제자리 정렬의 해답, 힙 정렬(Heap Sort)  (3) 2025.07.24
"느린 정렬"은 정말 항상 느릴까? (feat. 버블, 삽입 정렬의 재발견)  (1) 2025.06.28
같은 시간 복잡도인데 왜 DFS가 BFS 보다 느릴까? - 스택, 힙, 캐시로 파헤치는 알고리즘의 실제 성능 (BOJ 21736)  (2) 2025.06.07
백트래킹 개념, 유망 함수와 가지치기, 예시 문제로 이해하기  (0) 2025.05.25
집합, 유니온 파인드 알고리즘, 개념과 구현 + 최적화 + 활용 예시까지 (시간 복잡도와 재귀 호출 스택 디테일 포함)  (0) 2025.05.04

관련글

티스토리툴바