병합 정렬

---

• 재귀용법을 활용한 정렬 알고리즘이다.

1. 리스트를 절반으로 나눠 비슷한 크기의 두 부분 리스트로 나눈다.
2. 각 부분 리스트를 재귀적으로 합병 정렬을 사용해 정렬한다.
3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

시간 복잡도

• depth를 i라 하고, 맨 위 단계를 0이라고 하자.
  • 다음 그림에서 n/$2^2$ 는 2단계 깊이라고 하자.
    • 각 단계에 있는 하나의 노드 안의 리스트 길이는 n/$2^2$ 가 된다.
    • 각 단계에는 $2^i$ 개의 노드가 있다.
  • 따라서, 각 단계는 항상 $2^i * \frac { n }{ 2^i } = O(n)$
  • 단계는 항상 $log_2 n$ 개 만큼 만들어지고, 시간 복잡도는 $O(log_2n)$이다.
  • 따라서, 단계별 시간 복잡도 $O(n) * O(log n) = O(n log n)$이 된다.

병합 정렬 구현

---

# 리스트를 병합해주는 함수
def mergeList(left, right):
    merged = list()
    left_index, right_index = 0, 0
    
    # 1. left, right 리스트가 둘 다 있을 때
    while len(left) > left_index and len(right) > right_index:
        if left[left_index] > right[right_index]:
            merged.append(right[right_index])
            right_index += 1
        else:
            merged.append(left[left_index])
            left_index += 1
    
    # 2. left 리스트만 남았을 때
    while len(left) > left_index:
        merged.append(left[left_index])
        left_index += 1
    
    # 3. right 리스트만 남았을 때
    while len(right) > right_index:
        merged.append(right[right_index])
        right_index += 1
    
    return merged

# 재귀 용법을 사용하여 리스트를 못 나눌 때까지 나누는 함수
def splitList(data_list):
    if len(data_list) <=1:
        return data_list
    
    split_point = len(data_list) // 2
    left = splitList(data_list[:split_point])
    right = splitList(data_list[split_point:])
    
    return mergeList(left, right)