병합 정렬(Merge Sort) - 정의 / 예시 코드

 

병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 알고리즘을 사용하여 배열을 정렬하는 효율적인 알고리즘입니다. 배열을 반으로 나누고, 각 부분 배열을 재귀적으로 정렬한 후, 정렬된 부분 배열을 병합하여 최종적으로 정렬된 배열을 생성하는 방식으로 동작합니다.

아래는 병합 정렬의 동작 과정을 단계별로 설명한 것입니다.

 

1. 주어진 배열을 반으로 나눕니다. 이를 분할(Divide) 단계라고 합니다.

 

2. 각 부분 배열에 대해 재귀적으로 병합 정렬을 수행합니다. 부분 배열의 크기가 1 이하가 될 때까지 반복합니다.

 

3. 부분 배열을 정렬하고 나면, 정렬된 부분 배열을 병합(Merge)하여 크기가 더 큰 정렬된 부분 배열을 생성합니다.

 

4. 병합된 배열을 최종적으로 정렬된 배열로 반환합니다.

 

반응형

 

아래는 C++로 구현된 병합 정렬의 예시 코드입니다.

 

 

위의 예시 코드를 실행하면, 배열 {64, 25, 12, 22, 11}가 오름차순으로 정렬되어 {11, 12, 22, 25, 64}가 출력됩니다.

 

병합 정렬은 각 단계에서 배열을 반으로 나누는 분할(Divide) 단계와 정렬된 부분 배열을 병합하는 병합(Merge) 단계로 구성됩니다. 분할 단계에서 배열을 나누는 데에는 O(log n)의 시간이 소요되고, 병합 단계에서 배열을 병합하는 데에는 O(n)의 시간이 소요됩니다. 따라서 병합 정렬의 시간 복잡도는 항상 O(n log n)입니다. 또한, 병합 정렬은 안정적인 정렬 알고리즘으로 알려져 있습니다.