[Sort] Merge Sort (병합 정렬)

리스트를 반으로 나눈다. 가장 작은 조각으로 나누어졌을때(원소가 2개 이하) 정렬한다. 정렬된 두 리스트를 정렬한다.

 

정의

1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
5. 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.

 

설명

• 여러개의 정렬된 자료의 집합을 병합하여 한개의 정렬된 집합으로 만드는 방식이다.
• 분할 정복 알고리즘을 활용하여 자료를 최소단위로 나눈 후에 차례 대로 정렬하여 최종 결과를 얻어내는 Top-Down 방식이다.
• 시간복잡도는 반으로 나누는 것 O(logn), 정렬하는 것 O(n) 으로 둘을 곱한 O(nlogn)의 시간 복잡도를 가진다.

 

미리보기

 

시간복잡도

• O(nlogn) : 최선 최대 최악 모두

 

구현

✅ 분할

def merge_sort(m):
  if len(m) == 1:
  return m

  middle = len(m) // 2
  left = merge_sort(m[:middle])
  right = merge_sort(m[middle:])

  return merge(left, right)

 

✅ 정복

def merge(left, right):
  result = []
  l, r = 0, 0
  while l < len(left) or r < len(right): # 미정렬 원소가 하나라도 남은 경우
    if l < len(left) and r < len(right): # 둘다 미정렬 원소가 있는 경우
      if left[l] <= right[r]:
      	result.append(left[l])
      	l += 1
      else:
      	result.append(right[r])
      	r += 1
    elif l < len(left): # 왼쪽만 남은 경우(오른쪽은 인덱스 끝)
    	result.append(left[l])
    	l += 1
    elif r < len(right): # 오른쪽만 남은 경우(왼쪽은 인덱스 끝)
    	result.append(left[l])
    	l += 1

  return result

 

출처

위키 :  https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC