합병 정렬(Merge sort)

이번 포스팅에서는 합병 정렬(Merge sort)에 대해 알아 보겠습니다.

합병 정렬(Merge sort)은 하나의 리스트를 두 개의 균등한 크기로 분할하고,

분할 된 두 부분 리스트를 정렬한 다음, 두 개의 정렬 된 부분 리스트를 합하여

전체가 정렬 된 리스트가 되게 하는 방법이다. 

합병 정렬은 분할 정복(Divide and Conquer)방법에 바탕을 두고 있다.

분할 정복 방법은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서

원래의 문제를 해결하는 전략이다. 분리 된 문제가 아직도 해결하기 힘들다면,

즉 충분히 작아지지 않았다면 분할 정복 방법을 연속하여 다시 적용한다.

분할 정복 방법은 대개 순환 호출을 이용하여 구현 된다.

간단히 설명하자면 아래와 같은 단계로 이루어 진다.

1. 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.

2. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면

순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.

3. 결합(Combine) : 정렬 된 부분 배열들을 하나의 배열에 합병한다.

1. 분할 단계 : 배열을 27 10 12 20과 25 13 15 22의 2개의 부분 배열로 나눈다.

2. 정복 단계 : 부분 배열의 크기가 충분히 작아 질 때 까지 순환 호출을 이용한다.(배열의 길이가 0 또는 1)

그 후 부분 배열을 정렬하여 10 12 20 27과 13 15 22 25를 얻는다.

3. 결합 단계 : 부분 배열을 통합하여 10 12 13 15 20 22 25 27을 얻는다.

위 동영상을 보면 합병 정렬의 순서를 이해하기 쉬울 것이다.

합병 정렬의 소스 코드이다.

위 소스 코드에서 보이는 것과 같이 임시 배열을 이용하기 때문에

공간적인 낭비가 있다. 하지만 이를 보완 한 방법이 제자리 정렬법이다.

제자리 정렬은 입력은 저장하는 데 필요한 장소 이외의 추가적인 저장 장소를

사용하지 않는 정렬 알고리즘이다.

합병 정렬은 순환 호출 구조로 되어 있다. 따라서 레코드의 개수 n이 2의 거듭제곱이라고 가정하고

순환 호출의 깊이가 얼마나 되는지를 분석하였다. 만약 n=8인 경우에는 

부분 배열의 크기가 2^3 -> 2^2 -> 2 -> 1 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다.

따라서 일반적으로 이라고 하면 순환 호출의 깊이가 k가 될 것임을 쉽게 알 수 있다.

여기서 임을 알 수있다.

배열이 부분 배열로 나누어지는 단계에서는 비교 연산과 이동 연산은 수행 되지 않는다.

부분 배열이 합쳐지는 merge 함수에서 비교 연산과 이동 연산이 수행 되는 것이다.

순환 호출의 깊이 만큼의 합병 단계가 필요하다. 그러면 각 합병 단계에서 비교 연산은 몇 번이나 수행되는 것 일까?

이전의 예제인 n=2^3인 경우를 살펴보면 크기 1인 부분 배열 2개를 합병하는 데는 최대 2개의 비교 연산이 필요하고,

부분 배열의 쌍이 4개 이므로 2*4=8번의 비교 연산이 필요하다. 다음 단계에서는 크기가 2인 부분 배열을

2개를 합치는 데 최대 4번의 비교 연산이 필요하고, 부분 배열 쌍이 2쌍이 있으므로 역시 4*2=8번의 연산이 필요함을

알 수 있다. 마지막 합병 단계인 크기가 4인 부분 배열 2개를 합병하는 데는 최대 8번의 비교 연산이 필요하다.

따라서 또한 8*1번의 연산이 필요함을 알 수 있다.

일반적인 경우를 유추해보면 하나의 합병 단계에서는 최대 n번의 비교 연산이 필요함을 알 수 있다.

그러한 합병 단계가 번 만큼 있으므로 총 비교 연산은 최대 번 필요하다.

결론적으로 합병 정렬은 비교 연산과 이동 연산의 경우 의 복잡도를 가지는 알고리즘이다.

합병 정렬의 다른 장점은 안정적인 정렬 방법으로 데이터의 분포에 영향을 덜 받는다는 것이다.

즉 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다는 것이다.

최악, 평균, 최선의 경우가 다같이 인 정렬 방법이다.

출처 : C언어로 쉽게 풀어 쓴 자료구조

이상으로 합병 정렬에 대해 알아 보았습니다.

다음 퀵 정렬(Quick sort)를 마지막으로 정렬에 대한 포스팅은 마치도록 하겠습니다.