병합 정렬 (Merge Sort)

병합 정렬(Merge Sort)은 분할 정복(divide and conquer) 기법을 사용한 정렬 알고리즘으로,

 

주어진 배열을 반으로 나누어 재귀적으로 정렬한 다음, 두 개의 정렬된 배열을 병합하여 하나의 정렬된 배열을 만듭니다.

 

아래는 병합 정렬의 동작 과정을 나타낸 그림입니다.

출처: https://en.wikipedia.org/wiki/Merge_sort#Algorithm

 

1. 주어진 배열을 반으로 나누어 두 개의 배열로 만듭니다.
2. 각각의 배열을 재귀적으로 정렬합니다.
3. 두 개의 정렬된 배열을 병합하여 하나의 정렬된 배열을 만듭니다.

병합 정렬의 시간 복잡도는 O(nlogn)으로, 대부분의 경우에 퀵 정렬과 함께 가장 빠른 정렬 알고리즘 중 하나입니다.

 

그러나 정렬하려는 배열의 크기가 매우 크면, 재귀 호출의 깊이가 깊어져서 스택 오버플로(stack overflow)가 발생할 수 있습니다.

 

이러한 경우에는 힙 정렬(Heap Sort)이나 퀵 정렬(Quick Sort) 등 다른 정렬 알고리즘을 고려해 볼 수 있습니다.