TIL : 병합 정렬

병합 정렬

• 기존 데이터를 원소의 개수가 동일한 부분 리스트로 분할하고 분할된 각 부분 리스트를 병합하면서 정렬하는 방식

• 이는 정복 알고리즘(divide and conquer)에 해당

• 알고리즘 절차

  1. 하나의 리스트를 균등한 크기( 절반)로 반복해서 분할
     1. 각 요소들이 한 개씩 남을 때 까지
  2. 분할된 부분 리스트를 정렬
  3. 두 리스트를 합하여 전체가 정렬된 리스트 생성
     1. 원소의 갯 수가 2의 배수가 되는 만큼 합친다
     2. ex) 1개 + 1개 = 2개, 2개 + 2개 = 4개
  4. 이 때 합치는 순간에 정렬을 수행한다.

• O(n*logn)을 보장한다.

def merge(left, right):
    i, j = 0,0
    sorted_list = []
    
    while i < len(left) and j < len(right):
    	if left[i] < right[j]:
            sorted_list.append(left[i])
            i += 1
        else:
            sorted_list.append(right[j])
            j += 1
    while i < len(left):
    	sorted_list.append(left[i])
        i += 1
    while j < len(right):
    	sorted_list.append(right[j])
        j += 1
    return sorted_list
    
    
def merge_sort(unsorted_list):
    # 크기가 1이하면 반환
    if len(unsorted_list) <= 1:
    	return unsorted_list
     
    # 리스트를 2분할
    mid = len(unsorted_list)//2
    left = unsorted_list[:mid]
    right = unsorted_list[mid:]
    
    # 2분할한 리스트를 각각 merge sort진행
    left_ = merge_sort(left)
    right_ = merge_sort(right)
    return merge(left_, right_)

재귀함수를 이용하여 구현하는 것이 divide&conquer 알고리즘 구현에 더 적합하다.