병합 정렬 알고리즘이란?

오늘은 정렬 알고리즘 중 병합 방식을 활용한 정렬 알고리즘인 병합 정렬에 대해 소개하려고 한다

참고로 병합 정렬은 분할 후 정복하는 방식을 사용하여 리스트를 정렬하는 알고리즘이다

병합 정렬이란?

병합 정렬은 리스트를 반으로 나눈 후 나눠진 리스트를 다시 정렬하고 이렇게 정렬된 리스트들을 병합하는 방식으로 동작한다

알고리즘의 가장 큰 특징은 재귀적으로 리스트를 반으로 나누는 분할 과정과 이후 병합 과정에서 정렬이 이루어진다는 것이다

병합 정렬의 작동 방식

글로만 보면 잘 이해가 안될 수 있으니 예시를 들어 설명해보면

정렬해야 하는 리스트: [38, 27, 43, 3, 9, 82, 10] 첫 단계에서는 리스트를 두 부분으로 나눈다

첫 번째 진행:

[38, 27, 43, 3]와 [9, 82, 10]

두 번째 진행:

[38, 27]와 [43, 3], 그리고 [9, 82]와 [10]

세 번째 진행:

[38]와 [27], [43]와 [3], [9]와 [82], 그리고 [10]

이제 각 리스트의 원소가 1개뿐이므로 정렬된 상태로 간주하고 병합과정을 시작한다

이와 같은 과정을 반복하면 리스트에 전체 원소가 오름차순으로 정렬된다

병합 정렬의 장단점

마지막으로 병합 정렬 알고리즘에 장단점을 알아보자

장점:

1. 데이터의 크기가 크더라도 시간 복잡도가 O(n log n)으로 안정적이다
2. 안정 정렬(Stable Sort)이다

단점:

1. 추가적인 메모리 공간이 필요하다
2. 데이터의 양이 작을 경우 다른 알고리즘(예: 삽입 정렬)에 비해 상대적으로 느릴 수 있다