병합 정렬

2025-09-03 22:54

Tags:알고리즘

병합 정렬 (머지 소트, Merge Sort)

• 분할 정복을 쓰는 대표적인 정렬 알고리즘
• 모든 시간 복잡도 O(n log n)

구조

1. 분할
   1. 배열 반으로 나눔
   2. 더이상 못 나눌때까지 계속 재귀 호출로 쪼갬
2. 정복
   1. 각 하위 배열이 단위 요소면 이미 정렬되었으니 반환
3. 병합
   1. 나눠진 하위배열들을 하나씩 잡아서 합침
   2. 각 첫요소 비교 → 작은값 왼쪽 반복 → 두 배열 하나 합쳐짐
   3. 전체 하위 배열들에 모두 같은 작업 반복해서 최종 배열 반환

파이썬 코드

3. Python 구현 예제

모든 경우 O(n log n) 보장

구분	시간 복잡도	공간 복잡도	안정성
최선	O(n log n)	O(n)	안정적
평균	O(n log n)	O(n)	안정적
최악	O(n log n)	O(n)	안정적

References

배열 퀵 정렬 합병 정렬(Merge Sort) 핸드북