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

병합정렬(합병정렬) 이란?​

비교 기반의 정렬로, 안정 정렬에 속하며 분할 정복(Divide and Conquer) 알고리즘 중 하나이다.

 

※ 분할 정복(Divde and Conquer) 이란?

: 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결한 후, 결과를 모아 원래의 문제를 해결하는 전략.

 

병합정렬의 전체적인 과정

그래서, 병합정렬의 전체적인 과정은 다음과 같이 요약할 수 있다.

1. 정렬되지 않은 리스트를 각각 1개의 원소만 포함하는 n개의 부분리스트로 분할한다.
2. 분할된 부분리스트들을 병합(Merge)하며 정렬한다.
   그럼 다시 결국 1개의 리스트가 될 것이고 이 리스트는 정렬된 상태일 것이다.

 

병합정렬의 세부 과정

1. 분할(Divide) : 정렬되지 않은 리스트를 절반으로 분할하여 비슷한 크기의 두 리스트로 만든다.
   모든 리스트의 길이가 1이 될 때 까지 반복해서 분할 한다.
2. 정복(Conquer) : 쪼개진 각 부분 리스트들을 정렬하며 합병해나간다.
3. 결합(Combine) : 최종적으로 다시 하나의 정렬된 리스트로 결합한다.

 

이 과정을 그림으로 한번 살펴보자.

참고 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

병합정렬 코드

​그럼, 파이썬으로 나타낸 코드와 함께 살펴보자.

def merge_sort(list):
	# 길이가 1이면(보다 작으면) 정렬된 것으로 봄.(정렬필요X)
	if len(list) <= 1:
    	return list
    
    # 두개의 분할 리스트로 쪼갬
    mid = len(list) // 2
    left = list[:mid]
    right = list[mid:]
    
    # 쪼갠 각각의 리스트에 대해 길이가 1이 될 때 까지 반복 수행(재귀)
    left = merge_sort(left)
    right = merge_sort(right)
    
    # 쪼갠 리스트들을 정렬해가며 병합하는 함수 호출
    return merge(left, right)

def merge(left, right):
	# 정렬될 요소를 넣을 새 리스트
    result = []
    
    # 왼쪽, 오른쪽 리스트 모두 빌 때 까지 반복
    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
        	# 첫 번째 값의 크기를 비교하여 작은 값을 꺼내 새 리스트에 삽입
            if left[0] <= right[0]:
                result.append(left[0])
                left = left[1:]
            else:
                result.append(right[0])
                right = right[1:]
        
        # 한 리스트만 비었다면 남은 리스트의 값을 넣음
        elif len(left) > 0:
            result.append(left[0])
            left = left[1:]
        elif len(right) > 0:
            result.append(right[0])
            right = right[1:]
    
    # 정렬된 하나의 리스트 반환
    return result

 

 

병합정렬의 장단점​

• 장점
  
  • 안정 정렬(Stable Sort)로, 입력데이터가 무엇이든 시간복잡도는 O(nlogn)이다.
    그래서, 항상 동일한 시간이 소요되므로 어떤 경우에도 좋은 성능을 보장한다.
    -> 데이터의 분포에 영향을 덜 받는다.
• 단점
  • 제자리 정렬이 아니기 때문에, 별도의 추가적인 메모리가 필요하다.
  • 데이터가 많은 경우에는 이동 횟수가 많으므로 큰 시간적 낭비를 초래한다.

 

시간복잡도​

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

그럼 위 그림과 함께 어떻게 O(nlogn) 이라는 시간복잡도가 나왔는지 알아보자.

• 분할 단계 : 개수가 1 이 될 때 까지 쪼개기만 하므로 연산수행 X
• 병합 단계 :
  • 병합 단계의 깊이
    • 데이터의 개수 N이 2의 거듭제곱이라고 할 때,
      N=8 (2^3) 이라면, 8 -> 4 -> 2 ->1 개로 줄어 단계가 3임을 알 수 있다.
      N=16 (2^4) 이라면, 16 -> 8 -> 4 -> 2 -> 1 개로 줄어들어 4단계이다.
      
      즉, n=2^k의 경우, 깊이 k=log2​n임을 알 수 있다.
  • 비교 연산
    • 마찬가지로, N이 8 이라고 할 때,
      크기가 1인 부분 배열 2개를 합병하는데 최대 2번의 비교 연산이 필요하며
      쌍이 4개 이므로 2 x 4 = 8번의 비교 연산이 필요하다.
      
      
    • 그 다음 단계에서는, 크기가 2인 부분배열 2개를 합병하는데 최대 4번의 비교연산이 필요하며
      쌍이 2개 이므로 4 x 2 = 8번의 비교 연산이 필요하다.
      
      즉, 각각의 병합 단계마다 최대 N번의 비교 연산을 수행한다.
  • 따라서 병합 단계의 깊이 x 각 단계의 비교 연산= log2​n x N 이다.
  • 이를 빅오 표기법으로 표기하면 O(nlogn) 이다.

참고 자료​

• 병합정렬
• 합병정렬