DSA Interview Prep · 강의

병합 정렬: 분할, 정렬, 병합

Q: “병합 정렬: 분할, 정렬, 병합” 강의는 무료인가요?

네 — “병합 정렬: 분할, 정렬, 병합” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

Q: DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.

Q: “병합 정렬: 분할, 정렬, 병합” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

Q: 이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

병합 정렬을 재귀적으로 구현하고 분할 정복 트리를 추적하며, 모든 경우에 O(n log n)을 보장하는 이유를 설명합니다.

병합 정렬: 분할, 정렬, 병합은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

분할 정복의 직관

병합 정렬은 대표적인 분할 정복 알고리즘입니다. 배열을 절반으로 나누고, 각 절반을 재귀적으로 정렬한 다음, 정렬된 두 절반을 하나의 정렬된 결과로 merge합니다. 핵심 통찰은 정렬된 두 배열을 병합하는 데 O(n)만 필요하므로 처음부터 정렬하는 것보다 훨씬 저렴하다는 점입니다. 이 분해는 log n개 수준의 재귀 트리를 만들고 각 수준에서 O(n)의 병합 작업을 수행하므로, 비교 기반 정렬의 최적 한계인 O(n log n)을 얻습니다.

# High-level merge sort structure
def merge_sort(arr):
    # Base case: 0 or 1 element already sorted
    if len(arr) <= 1:
        return arr
    # Divide
    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])   # sort left half
    right = merge_sort(arr[mid:])   # sort right half
    # Conquer (merge)
    return merge(left, right)

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

병합 단계 설명

정렬된 두 배열을 병합할 때는 각 절반에 하나씩 두 포인터를 유지합니다. 앞에 있는 원소를 비교하고, 더 작은 원소를 출력에 copy한 다음 해당 포인터를 이동합니다. 한쪽 절반을 모두 처리하면 다른 절반의 나머지 원소를 그대로 copy합니다. 이 작업은 O(n) 시간과 출력 배열에 필요한 O(n) 공간을 사용합니다. 병합 단계는 병합 정렬의 알고리즘적 핵심이므로 깊이 있게 이해해야 합니다.

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= preserves stability
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # Append remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge([1,3,5,7], [2,4,6,8]))
# [1, 2, 3, 4, 5, 6, 7, 8]

병합 정렬 전체 구현

나누기와 병합을 결합합니다. 재귀 호출은 원소 하나만 남을 때까지 문제를 절반으로 나눕니다(이 상태에서는 자명하게 정렬되어 있습니다). 그런 다음 병합 호출이 이를 다시 결합합니다. 재귀 트리의 각 수준에서는 여러 병합에 분산되어 있더라도 총 n개의 동일한 원소를 병합합니다. 재귀 깊이는 log₂(n)이므로 전체 시간은 O(n log n)이고, 병합 출력 배열을 위한 O(n) 보조 공간과 O(log n) 호출 스택 깊이를 사용합니다.

def merge_sort_full(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left  = merge_sort_full(arr[:mid])
    right = merge_sort_full(arr[mid:])
    # Merge the two sorted halves
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]: merged.append(left[i]);  i += 1
        else:                   merged.append(right[j]); j += 1
    merged.extend(left[i:] + right[j:])
    return merged

print(merge_sort_full([5,2,4,6,1,3,2,6]))
# [1, 2, 2, 3, 4, 5, 6, 6]

병합 정렬 재귀 트리

n=8일 때 병합 정렬의 재귀 트리를 시각화해 보십시오. 수준 0에는 원소 8개인 배열 하나가 있고, 수준 1에는 원소 4개인 배열 두 개, 수준 2에는 원소 2개인 배열 네 개, 수준 3에는 원소 하나씩인 배열 여덟 개(기본 사례)가 있습니다. 다시 위로 올라가면 수준 3→2에서는 총 8개의 원소를 병합하고, 수준 2→1에서도 총 8개를 병합하며, 수준 1→0에서도 총 8개를 병합합니다. 즉, 수준 3개 × 원소 8개 = 연산 24회 ≈ 8 × log₂(8) = 24입니다. 이를 통해 O(n log n)임을 확인할 수 있습니다.

# Trace the tree depth
level_work = []

def merge_sort_traced(arr, depth=0):
    if depth >= len(level_work):
        level_work.append(0)
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left  = merge_sort_traced(arr[:mid],  depth+1)
    right = merge_sort_traced(arr[mid:],  depth+1)
    level_work[depth] += len(arr)  # track merge work
    merged = sorted(left + right)  # simplified merge
    return merged

merge_sort_traced(list(range(8, 0, -1)))
for d, work in enumerate(level_work):
    print(f'Level {d}: {work} elements merged')

제자리 병합 정렬

표준 재귀 병합 정렬은 병합 결과를 저장하기 위해 O(n) 보조 공간을 할당합니다. 제자리 병합 정렬도 존재하지만 복잡하고 상수 계수가 높아 면접에서는 거의 묻지 않습니다. 면접에서 흔히 이어지는 질문은 다음과 같습니다. '병합 정렬을 추가 공간 O(1)로 구현할 수 있나요?' 올바른 답은 다음과 같습니다. '이론적으로는 가능하지만, 실제 구현에서는 O(n) 공간을 사용하거나 복잡성이 증가합니다. 파이썬의 팀소트는 병합에 O(n) 공간을 사용합니다.'

# Bottom-up merge sort: iterative, avoids recursion stack
def merge_sort_bottomup(arr):
    n = len(arr)
    width = 1
    while width < n:
        for i in range(0, n, 2 * width):
            left  = arr[i:i+width]
            right = arr[i+width:i+2*width]
            # Merge and put back
            merged = []
            a, b = 0, 0
            while a < len(left) and b < len(right):
                if left[a] <= right[b]: merged.append(left[a]);  a+=1
                else:                   merged.append(right[b]); b+=1
            merged += left[a:] + right[b:]
            arr[i:i+len(merged)] = merged
        width *= 2
    return arr

print(merge_sort_bottomup([5,2,4,6,1,3]))
# [1, 2, 3, 4, 5, 6]

병합 정렬은 안정적입니다

병합 정렬은 안정적입니다. 즉, 병합된 결과에서 왼쪽 절반의 동일한 원소는 항상 오른쪽 절반의 동일한 원소보다 앞에 나타납니다. 왼쪽 원소를 우선할 때 <=(<가 아님)를 사용하면 안정성이 보장됩니다. 안정성은 여러 키로 정렬할 때 중요합니다. 파이썬의 내장 sorted()와 list.sort()는 안정적이고 O(n log n)인 팀소트를 사용하므로, 모든 실제 코드에서 안전한 선택입니다.

# Demonstrating stability: sort (value, original_index) pairs
items = [(3,'A'), (1,'B'), (3,'C'), (2,'D')]
# Sort by value only
result = merge_sort_full(items)  # won't work directly
# Use Python's stable sort:
result = sorted(items, key=lambda x: x[0])
print(result)
# [(1,'B'),(2,'D'),(3,'A'),(3,'C')]
# 'A' comes before 'C' for value=3 (stable order)

정렬된 k개 배열 병합

총 n개의 원소를 포함하는 정렬된 k개 배열은 쌍을 반복해서 병합하는 방식(토너먼트 대진표와 유사)으로 O(n log k) 시간에 병합할 수 있습니다. 각 병합 수준에서는 n개의 원소를 처리하고, 수준은 log k개입니다. 또는 크기가 k인 최소 힙을 사용할 수 있습니다. 각 배열에서 남아 있는 가장 작은 원소를 넣고, 최솟값을 꺼낸 다음, 해당 배열의 다음 원소를 넣습니다. 힙 방식도 O(n log k)이지만 k가 매우 클 때 메모리 효율이 더 높습니다.

import heapq

def merge_k_sorted(arrays):
    result = []
    heap = []
    # Push first element from each array with array index
    for i, arr in enumerate(arrays):
        if arr:
            heapq.heappush(heap, (arr[0], i, 0))
    while heap:
        val, arr_i, elem_i = heapq.heappop(heap)
        result.append(val)
        if elem_i + 1 < len(arrays[arr_i]):
            next_val = arrays[arr_i][elem_i + 1]
            heapq.heappush(heap, (next_val, arr_i, elem_i+1))
    return result

arrs = [[1,4,7],[2,5,8],[3,6,9]]
print(merge_k_sorted(arrs))  # [1,2,3,4,5,6,7,8,9]

병합 정렬로 역순쌍 세기

O(n log n)에 역순쌍( a[i] > a[j]이고 i < j인 쌍)을 세려면 수정된 병합 정렬을 사용합니다. 병합 단계에서 오른쪽 부분 배열의 원소가 왼쪽 부분 배열의 원소보다 작으면, 왼쪽 부분 배열에 남아 있는 모든 원소와 역순쌍을 이룹니다. 그 순간 개수에 len(left) - i를 더합니다.

def count_inversions(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left,  l_inv = count_inversions(arr[:mid])
    right, r_inv = count_inversions(arr[mid:])
    merged = []
    inversions = l_inv + r_inv
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
            inversions += len(left) - i  # all remaining left elements > right[j]
    merged.extend(left[i:] + right[j:])
    return merged, inversions

_, inv = count_inversions([3, 1, 2])
print(inv)  # 2: (3,1) and (3,2)

병합 정렬과 퀵 정렬 비교

병합 정렬은 모든 경우에 O(n log n)을 보장하고 안정적이며, 연결 리스트와 외부 정렬에 더 적합합니다. 퀵 정렬은 평균적으로 O(n log n)이지만 최악의 경우 O(n²)이고, 제자리에서 동작하며(O(log n) 스택 공간), 배열에서 캐시 효율이 높아 실제로는 더 빠른 경우가 많습니다. 파이썬의 내장 정렬은 팀소트(병합 정렬 변형)를 사용하므로 항상 올바른 기본 선택입니다.

# Head-to-head complexity comparison:
# Algorithm     | Best  | Avg      | Worst  | Space  | Stable
# Bubble sort   | O(n)  | O(n^2)   | O(n^2) | O(1)   | Yes
# Insertion sort| O(n)  | O(n^2)   | O(n^2) | O(1)   | Yes
# Merge sort    | O(nlogn)| O(nlogn)| O(nlogn)| O(n) | Yes
# Quick sort    | O(nlogn)| O(nlogn)| O(n^2) | O(logn)| No
# Heap sort     | O(nlogn)| O(nlogn)| O(nlogn)| O(1) | No

print('Merge sort: stable, O(n log n) guaranteed, O(n) space')

외부 정렬: 대규모 병합 정렬

병합 정렬은 외부 정렬(RAM에 담기에는 너무 큰 데이터를 정렬하는 방법)의 기반이 되는 알고리즘입니다. 데이터를 여러 조각으로 읽고, 각 조각을 메모리에서 정렬한 다음, 디스크에서 조각들을 병합합니다. 병합 단계에서는 정렬된 각 런에서 한 번에 원소 하나씩 읽으며, 동시에 메모리에는 O(k)개의 원소만 유지합니다(각 런에서 하나씩). 이것이 병합 정렬이 데이터베이스, 하둡 MapReduce, 전통적인 테이프 정렬 알고리즘에서 사용되는 이유입니다.

# Simulated external sort: sort in chunks then merge
def external_sort(data, chunk_size):
    chunks = []
    for i in range(0, len(data), chunk_size):
        chunk = sorted(data[i:i+chunk_size])  # sort in-memory
        chunks.append(chunk)
    print(f'Created {len(chunks)} sorted chunks')
    # Merge all chunks
    import heapq
    heap = [(c[0], i, 0) for i, c in enumerate(chunks) if c]
    heapq.heapify(heap)
    result = []
    while heap:
        val, ci, ei = heapq.heappop(heap)
        result.append(val)
        if ei + 1 < len(chunks[ci]):
            heapq.heappush(heap, (chunks[ci][ei+1], ci, ei+1))
    return result

print(external_sort(list(range(20,0,-1)), 5)[:10])

병합 정렬 요약 및 면접 팁

면접에서 병합 정렬을 깔끔하게 구현하면 재귀, 병합 단계, 분할 정복에 대한 이해를 보여 줄 수 있습니다. 흔히 이어지는 질문은 다음과 같습니다.

왜 O(n²)이 아니라 O(n log n)인가요? (log n개의 수준 × 수준마다 n개의 작업)
안정적인가요? (예, 병합에서 <=를 사용합니다)
공간을 얼마나 사용하나요? (O(n) 보조 공간 + O(log n) 스택)
반복문으로 구현할 수 있나요? (예, 상향식 병합 정렬을 사용하면 됩니다)
연결 리스트에는 어떻게 사용하나요? (배열보다 쉽습니다. O(n) 슬라이스 비용이 없고, 느린 포인터와 빠른 포인터를 사용해 중간 지점을 찾습니다)

# One-shot merge sort for interview clarity:
def ms(a):
    if len(a) <= 1: return a
    m = len(a) // 2
    l, r, res, i, j = ms(a[:m]), ms(a[m:]), [], 0, 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]: res.append(l[i]); i+=1
        else:             res.append(r[j]); j+=1
    return res + l[i:] + r[j:]

print(ms([5,2,4,6,1,3]))  # [1,2,3,4,5,6]

빠른 확인

이 학습에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보십시오.

학습 내용 정리

이 학습에서는 병합 정렬이 배열을 중간 지점에서 나누고, 각 절반을 재귀적으로 정렬한 다음, 정렬된 두 절반을 O(n)에 병합하여 log n개의 재귀 수준 전체에서 총 O(n log n)의 실행 시간을 만든다는 것, 병합 단계에서 동률일 때 왼쪽 원소를 선택하기 위해 <=를 사용하면 안정성이 보장된다는 것, 그리고 병합 정렬은 연결 리스트, 외부 정렬, 안정성이 필요한 경우에 적합한 알고리즘이며, 공간이 제한된 경우 메모리 내 배열에는 퀵 정렬이 선호된다는 것을 배웠습니다. 다음에는 퀵 정렬을 구현하고 피벗 선택 전략을 살펴봅니다.

자주 묻는 질문