[정렬] 합병(Merge) 소트

unsorted_list = [4,3,9,5,6]

def mergeSort(un_list):
    if len(un_list) <=1:
        return un_list
    
    mid = len(un_list) // 2
    left = un_list[:mid]  
    right = un_list[mid:]
    
    left2 = mergeSort(left)
    right2 = mergeSort(right)
    return merge(left2, right2)
    

def merge(left, right):
    i = 0
    j = 0 
    result = []
    while  (i < len(left)) & (j < len(right)):
        if left[i]  < right[j]:
            result.append(left[i])
            i+=1
        else:
            result.append(right[j])
            j+=1 
            

    while i < len(left):
        result.append(left[i])
        i+=1

    while j < len(right):
        result.append(right[j])
        j+=1
        
    return result    
        
        
            

print(mergeSort(unsorted_list))    
    
    
    

    
    
    

Merge Sort는 크게 두가지 과정을 거친다.

1. 분할 

- 분할할때 핵심은 재귀호출을 한다는 것이다.

2. Merge

- 재귀호출 이후에는 다시 분할된 리스트들을 다시 합치는 작업을 하는데, 해당 작업을 할때는 욎쪽 리스트와 오른쪽 리스트의 크기를 비교하여 정렬한 후 병합하는 작업을 한다. 

 

Merge Sort 이전에 공부 하였던 버선삽(버블, 선택, 삽입)정렬에 비해 복잡도가 크게 개선된 정렬이다. (n logn)