#합병정렬에 대해 알아보자. #merge_sort #정렬

    합병 정렬은 배열을 절반씩 나누어 그 각각을 정렬한 다음에, 다시 합하는 방식이다. 합병정렬은 Divide, Conquer, Combine 알고리즘으로 설명할 수 있다. 핵심 아이디어는 다음과 같다. 인풋으로 받는 리스트를 좌, 우로 나뉜 뒤(Divide)에 왼쪽 리스트와 오른쪽 리스트를 각각 정렬한뒤(Conquer), 이 정렬된 리스트를 하나로 합병하는 단계(Combine)로 구성되어 있다. 이 때 각각의 리스트는 정렬되어 있는 상태이다. 최종 합쳐진 리스트가 정렬되기 위해서는 각각 리스트 값의 첫번째 값들을 비교하여 하나로 합쳐야 한다. 

   정복(Conquer)부분이란,  부분 집합을 정렬해야 하는 단계이다. 부분 배열의 크기가 기준치 이하를 만족해야 한다. 그 크기는 0,1에 해당한다. 이 크기를 만족시키지 않으면, 순환 호출을 이용하여 다시 분할-정복 단계를 거친다.

그림 출처: https://en.wikipedia.org/wiki/Merge_algorithm

def merge_sort(my_list):
    # base case
    if len(my_list) < 2:
        return my_list

    # my_list를 반씩 나눈다(divide)
    left_half = my_list[:len(my_list)//2]    # 왼쪽 반
    right_half = my_list[len(my_list)//2:]   # 오른쪽 반


    # merge_sort 함수를 재귀적으로 호출하여 부분 문제 해결(conquer)하고,
    # merge 함수로 정렬된 두 리스트를 합쳐(combine)준다
    return merge(merge_sort(left_half), merge_sort(right_half))
    #print("merge", merge(merge_sort(left_half), merge_sort(right_half)))

 

 

def merge(list1, list2):
	i = 0
    j = 0 
    
    merge_list = []
    while (i <len(list1) and j<len(list2)): #두 리스트의 크기가 우리가 훑고자 하는 index값보다 클 때
    	if list1[i] < list2[j]:
        	merged_list.append(list1[i])
            i += 1 #i번째의 list1의 비교를 끝냈으면 다음값을 비교해야 한다. 
        
    	else : 
        	merged_list.append(list2[j])
            j += 1
    if i == len(list1): 
    	#리스트의 길이와 i의 값이 같다는 것은 list1 안에 있는 값들의 비교를 모두 끝냈다는 뜻이다.
    	merged_list.extend(list2[j:])
    elif j == len(list2):
    	merged_list.extend(list1[i:])
    return merged_list
  

 

위에서 보면, 최종적으로 정리된 리스트를 합쳐주는 부분이 return 부분에 구현되어 있다. 이 때의 merge 함수 부분은 input으로 받는 두 개의 리스트의 값을 하나씩 비교하여 새로운 리스트에 넣게 된다. merge의 함수는 구체적으로 아래와 같다. 아래의 함수는 '정렬된' list1, list2를 받아서 index를 하나씩 list1,2에 대해서 비교한 다음에 최종적으로 정렬한 list, merged_list를 리턴하게 된다.

 

위의 함수를 풀면서 가장 이해하기가 힘들었던 부분이 merge_sort함수의 return merge(merge_sort(left_half), merge_sort(right_half)) 부분이었다. merge_sort함수를 살펴보면, 재귀적으로 호출하여 my list의 크기가 1이하의 숫자일 때까지 나눈 다음에, 그 값을 list의 앞에서부터 차례대로 정렬하게 된다. 가장 작은 단위(리스트 크기가 1인) 경우부터 정렬되어서 차례대로 merge되어서 merge 함수의 리턴부분인 merged_list를 만든다고 이해하고 넘어갔다. 

 

평균 실행시간, 최악 실행 시간 : 모두 O(nlogn), 메모리 요구량은 상황에 따라 다르다.