Merge Sort (병합 정렬)

병합 정렬 (Merge Sort)

• 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식
• 분할 정복 알고리즘 활용
  • 자료를 최소 단위의 문제까지 나눈 후에 차례대로 정렬하여 최종 결과를 얻어냄
  • top-down 방식
• 시간 복잡도 : O(n log n)

 

병합 정렬 과정

• [69, 10, 30, 2, 16, 8, 31, 22] 를 병합 정렬하는 과정
• 분할 단계 : 전체 자료 집합에 대하여, 최소 크기의 부분집합이 될 때까지 분할 작업을 진행

 

• 병합 단계 : 2개의 부분집합을 정렬하면서 하나의 집합으로 병합
• 8개의 부분집합이 1개로 병합될 때까지 반복

 

• 분할 과정

def merge_sort(arr):
    # 리스트 길이가 1이면 최소 단위이므로 종료
    if len(arr) == 1:
        return arr
	
    # 중간 위치 찾기
    m = len(arr) // 2
    
    # 중간을 기준으로 왼쪽, 오른쪽 분할
    left_list = arr[:m]
    right_list = arr[m:]
	
    # 분할한 리스트를 정렬
    left_list = merge_sort(left_list)
    right_list = merge_sort(right_list)
	
    # 정렬된 두 리스트를 병합
    return merge(left_list, right_list)

 

• 병합 과정

def merge(left, right):
	# 분할한 리스트를 병합하기 위한 리스트
    result = []
	
    # 분할한 두 리스트의 대소비교를 하며 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