병합 정렬(Merge Sort)이란?
병합 정렬은 대표적인 정렬 기법 중 하나로, 시간 복잡도가 O(n log n)인 효율적인 정렬 알고리즘입니다. 여기서 n은 정렬해야 할 배열의 길이를 의미합니다.
병합 정렬은 분할 정복(Divide and Conquer) 패러다임을 따르는 알고리즘입니다. 배열을 계속해서 두 개의 절반으로 나눈 뒤, 요소가 하나씩만 남은 리스트들을 정렬하면서 지속적으로 병합하여 최종적으로 완전히 정렬된 리스트를 만들어냅니다.
동작 과정 예시
- 보라색 상자와 검은 화살표는 리스트를 두 부분으로 나누는(분할) 과정을 나타냅니다.
- 초록색 상자와 빨간 화살표는 정렬된 두 리스트를 합치는(병합) 과정을 나타냅니다.
이러한 분할과 병합 과정을 거치면 최종적으로 정렬된 배열을 얻을 수 있습니다.
파이썬으로 병합 정렬 구현하기
리스트를 두 부분으로 나누는 것은 비교적 간단하며, 요소가 하나만 남을 때까지 재귀적으로 수행됩니다. 이후에는 실질적인 핵심 로직인 병합(merge) 단계가 진행되는데, 이 단계에서 정렬된 두 리스트를 하나로 합치게 됩니다.
코드 예제
merge 함수는 병합할 두 개의 정렬된 배열(a1, a2)을 입력받습니다. a1의 맨 앞 요소와 a2의 맨 앞 요소를 서로 비교하여, 더 작은 값을 결과 리스트 c에 추가하고 해당 배열의 포인터를 한 칸 앞으로 이동시킵니다. 이 과정을 반복하면 두 배열이 이미 정렬되어 있기 때문에 전체적으로 정렬된 결과를 얻을 수 있습니다.
def merge(a1,a2): c=[] x=0 y=0 while(x<len(a1) and y<len(a2)): if(a1[x]<a2[y]): c.append(a1[x]) x+=1 else: c.append(a2[y]) y+=1 while(x<len(a1)): c.append(a1[x]) x+=1 while(y<len(a2)): c.append(a2[y]) y+=1 return c def mergesort(array): if(len(array)==1): return array mid=(len(array))//2 a1=mergesort(array[:mid]) a2=mergesort(array[mid:]) return merge(a1,a2) array=[2,3,1,5,4,6,8,10,7,9] print(mergesort(array))
실행 결과
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
병합 정렬의 특징 정리
- 안정 정렬(Stable Sort): 값이 같은 요소들의 원래 순서가 유지됩니다.
- 일관된 성능: 최선·평균·최악의 경우 모두 O(n log n)의 시간 복잡도를 가집니다.
- 추가 메모리 필요: 병합 과정에서 임시 배열을 사용하므로 공간 복잡도는 O(n)입니다.
- 재귀적 구조: 배열을 반으로 나누는 분할과 정렬된 결과를 합치는 병합이 재귀적으로 반복됩니다.