📌 병합 정렬이란?

• 병합 정렬을 구현하는 방법은 다음과 같다.
  1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
  2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
  3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

---

📌 병합 정렬 구현하기

• 병합 정렬은 아래의 2가지 과정으로 이루어진다.
  1. list를 절반으로 자르는 mergesplit 과정
  2. 쪼개진 2개의 list를 정렬하여 하나의 리스트로 합병하는 merge 과정
• 따라서 이 2개의 과정을 각각 mergesplit(data), merge(left, right) 함수로 구현하였다.

1. mergesplit(data) 구현하기

• mergesplit(data) : 리스트가 더이상 나뉘어지지 않을 때까지 리스트를 자르는 함수

def mergesplit(data):
- 만약 리스트 갯수가 한개이면 해당 값 리턴
- 그렇지 않으면, 리스트를 앞뒤, 두 개로 나누기
- left = mergesplit(앞)
- right = mergesplit(뒤)
- merge(left, right)

✅ mergesplit(data) Code

def mergesplit(data):
    if len(data) <= 1:
        return data
    medium = int(len(data) / 2)
    left = mergesplit(data[:medium])
    right = mergesplit(data[medium:])
    return merge(left, right)

2. merge(left, right) 구현하기

• merge(left, right) : left 와 right 의 리스트 데이터를 정렬해서 sorted_list 라는 이름으로 return하는 함수

1. sorted_list 리스트 변수 선언하기
2. left_index, right_index 를 0 으로 초기화 하기
3. while left_index < len(left) or right_index < len(right) 이면,
   - 만약 left_index >= len(left)이면, sorted_list 에 right[right_index] 를 추가하고, right_index 값을 1증가
   - 만약 right_index >= len(right)이면, sorted_list 에 left[left_index] 를 추가하고, left_index 값을 1증가
   - 만약 left[left_index] < right[right_index]이면, sorted_list 에 left[left_index] 를 추가하고, left_index 값을 1증가
   - 위 세가지가 아니면, sorted_list 에 right[right_index] 를 추가하고, right_index 값을 1증가

✅ merge(left, right) Code

def merge(left, right):
    merged = list()
    left_point, right_point = 0, 0
   
    # case1 - left/right 둘다 있을때
    while len(left) > left_point and len(right) > right_point:
        if left[left_point] > right[right_point]:
            merged.append(right[right_point])
            right_point += 1
        else:
            merged.append(left[left_point])
            left_point += 1

    # case2 - left 데이터가 없을 때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
      
    # case3 - right 데이터가 없을 때
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
 
    return merged

😉 이해가 잘 안된다면 여기를 클릭

---

📌 병합 정렬 시간 복잡도

• 병합 정렬의 시간 복잡도는 $O(n log n)$ 이다.