5. Array(배열) - Merge Sort(병합정렬)

1. Merge Sort란?

- 하나의 배열을 반씩 쪼개어, 배열의 요소를 각각의 배열로 만든다. 

- 독립적으로 쪼개진 배열을 비교해가며 병합하여 하나의 정렬된 배열을 만드는 알고리즘이다. 

 

a) 예제를 통한 병합정렬의 이해

 

b) 배열간의 요소를 비교하고 병합하는 과정

 

c) 병합정렬의 시간복잡도

---

2. 병합정렬 코드구현

# Merge Sort
# 1) Merge Sort의 개념 
#   - 하나의 배열을 반씩 쪼개어 요소의 총 개수만큼 독립된 배열을 만든다.
#   - 반씩 쪼개진 배열을 Left, Right로 구분한다. 
#   - Left에 있는 배열끼리, Right에 있는 배열끼리의 요소를 비교하여 병합한다.
#   - 비교 후 병합하는 과정을 반복하여 최종적으로 하나의 정렬된 배열을 만든다. 
#   - 이 과정을 재귀적으로 구현해낸다.  

# 2) Merge Sort의 시간복잡도(Time Complexity)
#   - 배열을 반씩 쪼개는 과정 => O(log n)
#   - 각각의 독립된 배열 요소간의 비교를 통한 병합과정 => O(n)
#   - 최종적으로 O(log n) * O(n) => O(n log n)의 시간복잡도를 갖는다. 

# 3) Merge Sort의 안정성(Stability)
#   - Merge Sort는 Stable한 정렬 알고리즘이다. 

# 4) Merge Sort 구현 
from typing import List

def merge_sort(case: List[int]) -> List[int]:

  # 반으로 쪼개기
  length = len(case)
  if length == 1:
    return case
  
  # 중간지점 index 찾기 
  mid = length // 2

  # 반으로 나누어 Left, Right로 분류하기 
  left_case = case[:mid]
  right_case = case[mid:]

  # 재귀적으로 length가 1일 때까지 반으로 나누고 정렬하기 
  # left_case부터 정렬을 시작한다.
  # left_case의 정렬이 완료된 후 right_case의 정렬이 시작된다.  
  sorted_left = merge_sort(case = left_case)
  sorted_right = merge_sort(case = right_case)

  # 비교 및 병합과정 
  sorted_case = []
  left_idx = 0
  right_idx = 0

  # 배열의 길이보다 작은 경우 = left_idx 또는 right_idx가 가리킬 다음 요소가 있는 경우
  while left_idx < len(sorted_left) or right_idx < len(sorted_right):

    # 만약 left_idx가 더이상 가리킬 다음 요소가 없는 경우 
    # right_idx가 현재 가리키는 수를 결과 배열에 병합한다. 
    if left_idx == len(sorted_left):
      sorted_case.append(sorted_right[right_idx])
      right_idx += 1
      continue

    # 만약 right_idx가 더이상 가리킬 요소가 없는 경우,
    # left_idx가 현재 가리키는 수를 결과 배열에 병합한다. 
    if right_idx == len(sorted_right):
      sorted_case.append(sorted_left[left_idx])
      left_idx += 1
      continue

    # 만약 right_idx가 가리키는 요소가 left_idx가 가리키는 요소보다 작은 경우,
    # right_idx가 가리키는 요소를 결과 배열에 병합한다. 
    if sorted_right[right_idx] <= sorted_left[left_idx]:
      sorted_case.append(sorted_right[right_idx])
      right_idx += 1
      continue

    # 만약 left_idx가 가리키는 요소가 right_idx가 가리키는 요소보다 작은 경우
    # left_idx가 가리키는 요소를 결과 배열에 병합한다. 
    else:
      sorted_case.append(sorted_left[left_idx])
      left_idx += 1
      
  return sorted_case

---

3. 병합정렬 정렬과정 분석 

- 병합정렬은 재귀함수로 구현되어 있기에, 코드를 이해하는데 있어서 어려움이 있을 수 있다. 

- 나 또한 재귀적 사고를 완벽히 할 줄 모르기에, 정렬과정을 직접 손으로 써내려가면서 이해하였다. 

- 다음 그림은 내가 직접 예시를 만들어서 손으로 정렬과정을 풀어본 것이다. 

- 나와 같은 어려움을 느끼는 분들에게 도움이 되기를 바란다.  

- 아래의 사진이 잘 안보이시는 분들을 위해, PDF파일을 공유합니다. 

병합정렬.pdf

6.14MB

 

a) 정렬과정

- 사진이 좌, 우 2장으로 구성되어 있습니다. 

- 좌측과 우측은 Left와 Right의 정렬과정을 각각 분리한 것입니다. 

- 좌측과 우측 사진을 분리하여 세로로 쭉 내려가면서 읽으시면 됩니다.