[Algorithm] 병합 정렬은 뭐야?

병합 정렬은 최악의 경우에도 O(NlogN)의 시간 복잡도를 보장하는 알고리즘으로 퀵 정렬보다 같거나 빠른 속도를 보여준다.

 

병합 정렬은 배열의 길이가 0 또는 1이 될 때까지 절반으로 나눈다. 나누어진 부분들을 병합하면서 각각의 배열에서 값을 하나씩 확인하면서 정렬을 한다.  해당 과정을 반복해서 정렬이 완료한다.

 

다음은 병합 정렬의 과정을 그림으로 나타낸 것이다. 

 

병합 정렬 1번째

1부터 8까지의 숫자를 무작위로 배치시킨 배열이다.

 

병합 정렬 2번째

더 이상 나눠지지 않을 때까지 배열을 반으로 나눈다.

 

병합 정렬 3번째

나눠진 배열을 정렬을 하면서 합친다. 위의 과정이 병합 정렬의 과정이다. 생각은 간단하다. 하지만 그렇기 때문에 코드는 간단하지 않다. 다음은 병합 정렬을 코드로 구현한 것이다.

 

# 병합 정렬 알고리즘
# 최악의 경우에도 O(NlogN)의 시간 복잡도를 보장한다.
array = [8,4,2,7,3,6,5,1]
 
def MergeSort(array):
  if len(array) <= 1:
    return array
  mid = len(array) // 2
  left = MergeSort(array[:mid])
  right = MergeSort(array[mid:])
  i, j, k = 0, 0, 0
 
  while i < len(left) and j < len(right):
    if left[i] < right[j]:
      array[k] = left[i]
      i += 1
    else:
      array[k] = right[j]
      j += 1
    k += 1
  if i == len(left):
    while j < len(right):
      array[k] = right[j]
      j += 1
      k += 1
  elif j == len(right):
    while i < len(left):
      array[k] = left[i]
      i += 1
      k += 1
  return array
 
array = MergeSort(array)
print(array)

 

알고리즘을 공부하면서 느낀 것이지만 재귀 함수가 굉장히 편하고 많이 사용되는 것 같다. 파이썬은 코드 9, 10번째 줄에서 볼 수 있듯이 배열을 인덱스에 맞춰 자르는 게 편하다. 그리고 left, right에 array의 값을 모두 저장하므로 따로 배열을 생성할 필요 없이 array에 직접 값을 바꿔주는 방식을 취한다.

 

병합 정렬은 빠른 속도와 간단한 생각으로 이해하기는 쉽지만 구현하기에는 어려운 것 같다.