합병 정렬

Python으로 배우는 자료구조와 알고리즘

Miriam Antona

Software engineer

합병 정렬

분할 정복 방식
- 분할
  - 문제를 더 작은 하위 문제로 나눕니다
- 정복
  - 하위 문제를 재귀적으로 풉니다
- 결합
  - 하위 문제 해를 결합해 최종 해를 얻습니다

합병 정렬 - 동작 예시

정렬되지 않은 숫자 목록의 도식.

합병 정렬 - 동작 예시

정렬되지 않은 숫자 목록의 도식. 리스트가 두 부분으로 나뉨.

합병 정렬 - 동작 예시

정렬되지 않은 숫자 목록의 도식. 리스트가 두 부분으로 나뉨. 새 두 리스트 중 첫 번째는 원본의 왼쪽 절반, 두 번째는 오른쪽 절반을 가짐.

합병 정렬 - 동작 예시

정렬되지 않은 숫자 목록의 도식. 새 리스트들이 두 부분으로 나뉨.

합병 정렬 - 동작 예시

정렬되지 않은 숫자 목록의 도식. 마지막으로 분할된 리스트들이 다시 나뉘어 새 리스트가 생성됨.

합병 정렬 - 동작 예시

정렬되지 않은 숫자 목록의 도식. 새 리스트들이 두 부분으로 나뉨.

합병 정렬 - 동작 예시

정렬되지 않은 숫자 목록의 도식. 마지막으로 분할된 리스트들이 다시 나뉘어 새 리스트가 생성됨.

합병 정렬 - 동작 예시

정렬되지 않은 숫자 목록의 도식. 새 리스트들이 두 부분으로 나뉨.

합병 정렬 - 동작 예시

정렬되지 않은 숫자 목록의 도식. 새 리스트들이 두 부분으로 나뉨.

합병 정렬 - 동작 예시

정렬되지 않은 숫자 목록의 도식. 마지막으로 분할된 리스트의 원소들이 정렬됨.

합병 정렬 - 동작 예시

정렬되지 않은 숫자 목록의 도식. 마지막으로 분할된 리스트의 원소들이 병합되어 정렬됨.

합병 정렬 - 동작 예시

정렬되지 않은 숫자 목록의 도식. 마지막으로 분할된 리스트의 원소들이 병합되어 정렬됨.

합병 정렬 - 동작 예시

정렬되지 않은 숫자 목록의 도식. 마지막으로 분할된 리스트의 원소들이 병합되어 정렬됨. 모든 원소가 정렬 완료.

합병 정렬 - 구현

def merge_sort(my_list):
  if len(my_list) > 1:

    mid = len(my_list)//2
    left_half = my_list[:mid]
    right_half = my_list[mid:]

    merge_sort(left_half)
    merge_sort(right_half)


    i = j = k = 0

    while i < len(left_half) and j < len(right_half):

      if left_half[i] < right_half[j]:

        my_list[k] = left_half[i]

        i += 1

      else:

        my_list[k] = right_half[j]

        j += 1

      k += 1

    while i < len(left_half):

      my_list[k] = left_half[i]
      i += 1
      k += 1


    while j < len(right_half):
      my_list[k] = right_half[j]
      j += 1
      k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)

[1, 4, 20, 22, 30, 35, 40, 50, 90]

합병 정렬 - 복잡도

최악: $O(n\log{}n)$
- 버블/선택/삽입 정렬보다 크게 개선
- 큰 리스트 정렬에 적합
평균: $\Theta(n\log{}n)$
최선: $\Omega(n\log{}n)$
- 다른 알고리즘(예: 버블, 삽입)은 최선의 경우 더 좋음
공간 복잡도: $O(n)$
- $O(1)$인 알고리즘보다 공간 사용이 큼
다른 변형은 공간 사용을 줄임

연습해 봅시다!

Python으로 배우는 자료구조와 알고리즘