알고리즘 | 합병 정렬 (Merge Sort)

합병 정렬 (Mearge Sort)

1. 개요

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.

합병 정렬은 분할 - (정복) - 결합의 단계로 이루어진다.

• 분할 : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
• 정복 : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용한다.
• 결합 : 정렬된 부분 배열들을 하나의 배열에 합병한다.

합병 정렬은 추가적인 리스트가 필요하며 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다. 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병하는 단계이다.

2. 예시

3. 시간복잡도

크기가 N인 배열을 반으로 쪼개면서 분할해 나가기 때문에 시간복잡도는 O(NlogN)이다.

크기가 N인 배열을 둘로 쪼개서 다시 정렬된 배열로 병합할 때는 비교의 횟수가 N번을 넘지 않는다.

길이가 N/2인 배열을 정렬하는데에는, N/4의 길이를 가지는 배열 두 개를 정렬하므로, 이것의 비교연산 횟수는 N/2이다.

전체로 보면, 길이가 N/4인 배열을 두개씩 합병하여 정렬된 N/2배열을 두 개 만드는 작업을 수행하는데 드는 비교연산의 횟수는 2*N/2 = N이다.

모든 경우 비교연산 횟수는 N이다. 길이가 N인 배열을 길이가 1인 각각의 리스트로 쪼개려면, 아래의 표에서 봤을 때 트리의 레벨은 logN이 된다.

따라서 총 횟수는 N*logN이다.