병합정렬 시각화
배열을 반으로 나누고, 정렬된 부분을 병합하는 과정을 관찰합니다
정렬★★☆
속도
1 / 1재귀 깊이: 0비교 횟수: 0병합 횟수: 0
배열 크기20
왼쪽 부분오른쪽 부분비교 중배치 중정렬 완료미정렬
배열이 분할되고 병합되는 과정을 단계별로 관찰하세요.
배열이 분할되고 병합되는 과정을 단계별로 관찰하세요.
병합정렬이란?
병합정렬(Merge Sort)은 배열을 반으로 나누고, 각 부분을 재귀적으로 정렬한 후, 두 정렬된 부분을 하나로 합치는 분할정복 알고리즘입니다. 항상 O(n log n) 시간 복잡도를 보장하며, 같은 값의 상대적 순서를 유지하는 안정 정렬입니다.
사용 방법
- 1배열 크기를 슬라이더로 조절하세요 (5~50)
- 2랜덤, 거의 정렬, 역순 버튼으로 다양한 입력을 생성하세요
- 3청록색은 왼쪽 부분배열, 주황색은 오른쪽 부분배열입니다
- 4노란색은 비교 중, 보라색은 병합 배치 중인 요소입니다
- 5코드 탭에서 분할-병합 과정의 실행 흐름을 추적하세요
동작 원리
- 1배열을 절반으로 분할(divide)합니다
- 2각 부분을 재귀적으로 병합정렬합니다
- 3크기 1이 되면 재귀가 종료됩니다
- 4두 정렬된 부분 배열을 하나로 병합(merge): 양쪽에서 작은 값을 순서대로 선택합니다
- 5모든 레벨에서 병합 완료 시 전체 정렬이 끝납니다
실무 활용
- •Python sorted()/list.sort()의 Timsort가 병합정렬 기반입니다
- •Java의 Arrays.sort(Object[])가 Timsort(병합정렬 변형)를 사용합니다
- •외부 정렬(External Sort) — 메모리보다 큰 파일 정렬 시 파일 조각을 병합할 때 사용됩니다
- •연결 리스트 정렬에 최적(인덱스 접근 없이 병합 가능)합니다
- •Git의 3-way merge가 병합정렬의 merge 단계와 유사한 원리입니다
비슷한 알고리즘
- •퀵정렬 — 평균적으로 더 빠르고 제자리 정렬이지만 최악 O(n²). 병합정렬은 항상 O(n log n)이나 O(n) 추가 메모리
- •힙정렬 — 제자리 + O(n log n) 보장이지만 캐시 효율이 낮아 실측은 병합정렬보다 느릴 수 있음
- •Timsort — 병합정렬 + 삽입정렬의 하이브리드. 이미 정렬된 부분(run)을 활용하여 실세계 데이터에서 매우 빠름
학습 팁
- •병합정렬은 입력 데이터에 관계없이 항상 O(n log n)입니다
- •분할 깊이가 log₂(n)번이고, 각 깊이에서 n개 요소를 병합합니다
- •퀵정렬과 달리 추가 메모리(O(n))가 필요합니다
- •안정 정렬이므로 같은 값의 원래 순서가 유지됩니다
자주 묻는 질문
Q. 퀵정렬과 어떤 차이가 있나요?
A. 병합정렬은 항상 O(n log n)이지만 추가 메모리 O(n)이 필요합니다. 퀵정렬은 평균 O(n log n), 최악 O(n²)이지만 제자리 정렬(O(1) 추가 메모리)입니다.
Q. 왜 안정 정렬이 중요한가요?
A. 데이터베이스에서 이름 정렬 후 나이 정렬할 때, 안정 정렬이면 같은 나이에서 이름 순서가 유지됩니다. Python의 sorted()와 Java의 Arrays.sort(객체)는 병합정렬 기반입니다.
Q. 언제 병합정렬을 사용하나요?
A. 안정 정렬이 필요할 때, 최악 케이스 보장이 필요할 때, 연결 리스트 정렬(추가 메모리 O(1))할 때 적합합니다.