[병합 정렬] Merge Sort - Python

병합 정렬 Merge Sort

Merge Sort

Merge Sort

시간복잡도는 Worst - O(NlogN), Average - O(NlogN), Best - O(NlogN)

Merge Sort의 경우 원래 리스트의 크기만큼의 추가공간이 필요하다.

입력 Data의 크기가 클 경우 Overhead가 증가할 수 있다.

Divide & Conquer 단계를 수행하므로 시간 복잡도는 LogN이다.

Merge Sort는 3단계로 구성된다.

1. 각 리스트를 절반으로 나누는 Divide 단계
2. 나눠진 리스트를 정렬하는 Conquer 단계
3. 정렬된 리스트를 하나로 합치는 Combine 단계

Merge Sort 작동 과정

def merge_sort(data):
  result = []
  # 중간 index 구하기
  mid = (len(data))//2

  # 재귀 종료 조건
  if len(data) < 2 :
    return data

  # 재귀 호출로 분할 : Divide
  left = merge_sort(data[:mid])
  right = merge_sort(data[mid:])

  # 나눠진 두 배열을 정렬 : Conquer
  i = j = 0
  while i<len(left) and j<len(right):
    if left[i] < right[j]:
      result.append(left[i])
      i = i+1
    else:
      result.append(right[j])
      j = j+1

  # 비교 후 남아 있는 값 병합 : Merge
  result += left[i:]
  result += right[j:]

  return result

data = [7,5,3,1,4,2,6,8]
merge_sort(data)

* Merge sort를 더 효율적으로 구현하기 위해서는 배열을 생성하는 과정 대신, 정렬시마다 기존 배열에 반영해 주어야 한다