병합 정렬 (Merge Sort)

배열을 반으로 나눠 정렬한 뒤 다시 합치는 병합 정렬을 막대 애니메이션으로 확인하세요. O(n log n)이 보장되는 이유와 임시 배열이 필요한 트레이드오프를 볼 수 있습니다.

알고리즘

배열

크기48
비교 중교환/쓰기피벗/기준읽기정렬 확정
속도50×

비교

0

교환/쓰기

0

스텝

0/535

읽기

0

보조 메모리

0

재귀 깊이

1/1

재생 속도를 늦추고 '한 단계'로 따라가며 의사코드 하이라이트와 막대 색을 비교해 보세요.

의사코드

mergeSort(lo, hi)

mid ← (lo+hi)/2

mergeSort(lo,mid) mergeSort(mid+1,hi)

while left & right remain

a[k] ← smaller of the two fronts

copy merged run back

시간 복잡도

최선O(n log n)
평균O(n log n)
최악O(n log n)
공간O(n)
안정O

병합 정렬은 대표적인 분할 정복 알고리즘입니다. 배열을 절반씩 계속 쪼개 원소 하나짜리 구간까지 내려간 뒤, 두 정렬된 구간의 앞 원소끼리 비교하며 작은 쪽부터 꺼내 합칩니다(병합). 막대가 왼쪽 구간부터 순서대로 다시 쓰이는 것이 이 병합 단계입니다.

분할 깊이가 log n이고 각 단계의 병합이 n개를 한 번씩 훑으므로 최선·평균·최악 모두 O(n log n)이 보장됩니다. 입력이 어떤 상태든 성능이 일정하다는 게 퀵 정렬과의 큰 차이입니다.

대신 병합 결과를 담을 임시 배열이 필요해 O(n) 추가 공간을 씁니다. 안정 정렬이라 같은 값의 순서가 유지되고, 연결 리스트나 외부 정렬처럼 순차 접근만 가능한 환경에서도 잘 동작합니다. 정렬 알고리즘 시각화에서 다른 알고리즘과 같은 배열로 비교해 보세요.

자주 묻는 질문

병합 정렬과 퀵 정렬 중 뭐가 좋은가요?
퀵 정렬이 평균적으로 캐시 효율과 상수항에서 빠르지만 최악 O(n²)의 위험이 있습니다. 병합 정렬은 최악에도 O(n log n)이 보장되고 안정 정렬이라, 안정성과 예측 가능한 성능이 필요하면 병합을 선택합니다.
병합 정렬은 왜 추가 메모리가 필요한가요?
두 정렬된 구간을 하나로 합칠 때 원본 위에서 바로 덮어쓰면 아직 읽지 않은 값이 지워지기 때문입니다. 병합 결과를 담는 임시 배열(O(n))이 필요하고, 이게 제자리 정렬이 아닌 이유입니다.
병합 정렬은 안정 정렬인가요?
네. 병합할 때 왼쪽 구간의 값을 먼저 꺼내는 규칙 덕분에 같은 값의 상대 순서가 유지됩니다.

다른 알고리즘 보기