병합 정렬
병합 정렬 (Merge Sort)
병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 패러다임을 사용하는 대표적인 정렬 알고리즘입니다. 어떤 입력 데이터에 대해서도 항상 O(n log n)의 안정적인 성능을 보장하며, 동일한 값을 가진 원소의 상대적 순서가 유지되는 안정 정렬(Stable Sort)이라는 큰 장점을 가집니다.
🧩 병합 정렬의 동작 원리
병합 정렬은 '분할'과 '병합'이라는 두 가지 핵심 단계로 이루어집니다.
1. 분할 (Divide) : 정렬되지 않은 배열을 더 이상 나눌 수 없을 때까지(배열의 크기가 1이 될 때까지) 재귀적으로 절반으로 나눕니다. 2. 정복 (Conquer) : 각 부분 배열은 크기가 1이므로 이미 정렬된 상태로 간주합니다. 3. 결합 (Combine) : 정렬된 두 개의 부분 배열을 하나의 정렬된 배열로 병합(merge)합니다. 이 과정을 재귀 호출의 역순으로 반복하여, 최종적으로 전체 배열이 정렬되도록 합니다.
- 병합 (Merge) 과정 : 병합 정렬의 핵심으로, 두 개의 정렬된 부분 배열을 순서대로 비교하며 하나의 정렬된 배열로 합치는 과정입니다. 이 과정에서 O(n)의 시간과 O(n)의 추가 공간이 필요합니다.
👍 병합 정렬의 장점과 단점
- 장점 (Advantages)
> * 안정 정렬 (Stable Sort) : 정렬 과정에서 동일한 값을 가지는 원소들의 상대적인 순서가 유지됩니다. > * 보장된 성능 : 입력 데이터의 상태와 상관없이 최선, 평균, 최악의 경우 모두 항상 O(n log n)의 시간 복잡도를 보장합니다.
- 단점 (Disadvantages)
> * 추가 공간 필요 : 정렬 과정에서 두 부분 배열을 합치기 위한 추가적인 배열(메모리)이 필요합니다 (O(n)). 즉, '제자리 정렬(In-place Sort)'이 아닙니다. > * 평균 속도 : 퀵 정렬에 비해 실제 실행 시간이 조금 더 느릴 수 있습니다. (데이터 복사 과정 때문)
💡 개발자 핵심 Point
- 병합 정렬은 안정성과 보장된 성능이 필요할 때 매우 유용한 알고리즘입니다.
- 퀵 정렬(Quick Sort)과의 비교
> * '병합 정렬': 추가 메모리 필요(O(n)), 안정 정렬, 항상 O(n log n) 보장. > * '퀵 정렬': 제자리 정렬, 불안정 정렬, 평균적으로 빠름, 최악의 경우 느림(O(n²)).
- 활용 사례
> * 데이터의 안정적인 순서 유지가 중요한 경우. (e.g., 사용자를 이름순으로 정렬한 뒤, 다시 가입일 순으로 정렬해도 이름순이 유지되어야 할 때) > * 연결 리스트(Linked List)를 정렬할 때 효율적입니다. 연결 리스트는 중간 삽입이 용이하여, 병합 과정에서 추가적인 공간 없이 정렬을 수행할 수 있습니다. > * 대용량 외부 데이터 정렬(External Sorting)에 사용됩니다. 메모리에 한 번에 올릴 수 없는 대용량 파일을 정렬할 때, 파일을 작은 조각으로 나누어 정렬(병합 정렬)하고, 정렬된 조각들을 다시 병합하는 방식으로 동작합니다.
