머지 소트
IT 위키
머지 소트(Merge Sort)는 분할 정복(divide and conquer) 방식의 정렬 알고리즘으로, 데이터를 반으로 나누어 정렬한 후 병합하는 방식으로 동작한다. 안정 정렬(stable sort)에 속하며, 평균 및 최악의 경우 시간 복잡도가 O(n log n)으로 일정하다. (Θ(n log n)
1 개요[편집 | 원본 편집]
머지 소트는 문제를 작은 부분으로 나누고, 이를 정렬한 후 병합하는 방식으로 동작한다. 알고리즘의 동작 과정은 다음과 같다.
- 리스트를 반으로 나눈다.
- 각각의 부분 리스트를 재귀적으로 정렬한다.
- 정렬된 두 리스트를 병합하여 하나의 정렬된 리스트를 만든다.
이 알고리즘은 재귀적으로 구현될 수도 있고, 반복문을 사용한 비재귀적(반복문) 방식으로도 구현될 수 있다.
2 알고리즘 과정[편집 | 원본 편집]
머지 소트의 동작 과정은 다음과 같다.
2.1 1. 분할 (Divide)[편집 | 원본 편집]
- 주어진 리스트를 두 개의 하위 리스트로 분할한다.
- 리스트의 크기가 1이 될 때까지 재귀적으로 나눈다.
예제: 정렬할 배열이 다음과 같다고 가정한다.
[38, 27, 43, 3, 9, 82, 10]
이 배열을 반으로 나누면 다음과 같이 된다.
[38, 27, 43, 3] [9, 82, 10]
이 과정을 계속 반복하면, 모든 부분 배열의 크기가 1이 될 때까지 나눠진다.
[38] [27] [43] [3] [9] [82] [10]
2.2 2. 정복 (Conquer)[편집 | 원본 편집]
- 각각의 하위 리스트를 개별적으로 정렬한다.
정렬된 두 개의 리스트를 병합하며 정렬을 수행한다.
1단계 병합 후:
[27, 38] [3, 43] [9, 10] [82]
2단계 병합 후:
[3, 27, 38, 43] [9, 10, 82]
2.3 3. 병합 (Merge)[편집 | 원본 편집]
- 두 개의 정렬된 리스트를 하나의 정렬된 리스트로 합친다.
최종 병합 과정 후:
[3, 9, 10, 27, 38, 43, 82]
이제 전체 리스트가 정렬되었다.
3 시간 복잡도[편집 | 원본 편집]
머지 소트의 시간 복잡도는 다음과 같이 분석할 수 있다.
- 최선의 경우(Best Case) : Ω(n log n)
- 평균적인 경우(Average Case) : Θ(n log n)
- 최악의 경우(Worst Case) : O(n log n)
머지 소트는 항상 O(n log n)의 시간 복잡도를 보장하며, 입력이 어떠한 순서로 되어 있더라도 성능이 일정하다.
4 공간 복잡도[편집 | 원본 편집]
머지 소트는 추가적인 메모리 공간이 필요하며, 재귀 호출과 병합 과정에서 O(n)의 추가 공간을 사용한다.
5 구현[편집 | 원본 편집]
다음은 파이썬(Python)으로 구현된 머지 소트 예제이다.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = merge_sort(arr[:mid])
right_half = merge_sort(arr[mid:])
return merge(left_half, right_half)
def merge(left, right):
sorted_arr = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
sorted_arr.append(left[i])
i += 1
else:
sorted_arr.append(right[j])
j += 1
sorted_arr.extend(left[i:])
sorted_arr.extend(right[j:])
return sorted_arr
# 사용 예제
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr) # 출력: [3, 9, 10, 27, 38, 43, 82]
6 머지 소트의 특징[편집 | 원본 편집]
- 안정 정렬(Stable Sort) : 동일한 값의 원소들이 정렬 후에도 상대적인 순서를 유지한다.
- 일관된 성능 : 최선, 평균, 최악의 경우 시간 복잡도가 O(n log n)으로 일정하다.
- 추가적인 메모리 사용 : 병합 과정에서 추가적인 메모리 공간이 필요하여 O(n)의 공간 복잡도를 가진다.
- 큰 데이터 정렬에 유리 : 퀵 정렬과 달리 최악의 경우에도 O(n log n)을 유지하여 안정적인 성능을 제공한다.
7 응용[편집 | 원본 편집]
머지 소트는 다음과 같은 상황에서 유용하게 사용된다.
- 연결 리스트(Linked List) 정렬 - 연결 리스트에서는 추가적인 메모리 사용이 상대적으로 적어 퀵 정렬보다 유리할 수 있음.
- 외부 정렬(External Sorting) - 데이터가 메모리에 한 번에 적재되지 않을 때 사용됨.
8 같이 보기[편집 | 원본 편집]
9 참고 문헌[편집 | 원본 편집]
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
- Knuth, D. E. (1997). The Art of Computer Programming. Addison-Wesley.
