Mrg
SORTING
병합 정렬 (Merge Sort)
배열을 절반씩 나눠 각각 정렬한 뒤 하나로 합치는 과정을 한 단계씩, 또는 자동 재생으로 직접 확인하세요. 배열 상태와 관계없이 항상 비슷한 속도로 동작한다는 점을 다른 정렬과 비교할 수 있습니다.
재생 버튼을 눌러 정렬을 시작하세요.
비교 0회 · 기록 0회
1 / 1
속도
대기
병합 구간
비교 중
방금 기록됨
정렬 완료
PSEUDOCODE (merge 단계)
merge(array, lo, mid, hi): i ← lo, j ← mid while i < mid and j < hi if array[i] ≤ array[j] 결과에 array[i] 기록, i ← i+1 else 결과에 array[j] 기록, j ← j+1 남은 값을 순서대로 이어서 기록어떻게 동작하나요
배열을 더 이상 나눌 수 없을 때까지(원소 1개) 절반씩 재귀적으로 나눈 뒤, 이미 정렬된 두 부분을 왼쪽부터 하나씩 비교하며 더 작은 값을 순서대로 옮겨 담습니다. 항상 O(n log n)을 보장하고 안정 정렬(같은 값의 순서 유지)이라는 장점이 있는 대신, 병합 과정에 원본과 같은 크기의 추가 공간이 필요하다는 트레이드오프가 있습니다.
시간·공간 복잡도
- 최선
- O(n log n)
- 평균
- O(n log n)
- 최악
- O(n log n)
- 공간 복잡도
- O(n)
- 안정 정렬
- 예 (Stable)
프리셋을 바꿔가며 비교·기록 횟수를 확인해보세요 — 버블·선택·삽입 정렬과 달리 배열 상태와 거의 무관하게 항상 O(n log n)입니다. 대신 O(1)이 아닌 O(n) 추가 공간이 필요합니다.
다른 정렬 알고리즘(버블·선택·삽입·퀵)도 함께 시각화되어 있습니다 — Algorithm 코스로 돌아가기