[알고리즘] 합병 정렬이란? (개념, 파이썬 코드)

합병 정렬(Merge Sort)이란?

배열을 2개의 하위 배열로 재귀적으로 나눈 후, 다시 각 배열을 합치면서 정렬한다.

분할 정복 (Divide and Conquer)에 해당한다.

*분할 정복이란?

문제를 작게 분할한 후 각각을 해결하고, 그 결과를 이용해 전체 문제를 해결하는 알고리즘

• 방법
  • 주어진 배열을 균등한 크기의 2개의 배열로 분할한다.
  • 분할된 부분 배열을 반복해서 2개의 배열로 분할한다.
  • 더 이상 분할할 수 없을 때, 다시 2개의 배열을 합쳐서 정렬한다. ([3], [1] -> [1, 3])
  • 재귀적으로 정렬된 부분 배열을 하나로 합치면서 전체가 정렬된 배열을 만든다. ([1, 3], [2, 4] -> [1, 2, 3, 4])

 

파이썬으로 구현하기

def merge_sort(arr, start, end):
    if start >= end:
        return

    mid = (start + end) // 2

    merge_sort(arr, start, mid)
    merge_sort(arr, mid + 1, end)
    merge(arr, start, mid, end)

def merge(arr, start, mid, end):
    i, j = start, mid + 1
    sorted_arr = []

    while i <= mid and j <= end:
        if arr[i] < arr[j]:
            sorted_arr.append(arr[i])
            i += 1
        else:
            sorted_arr.append(arr[j])
            j += 1

    while i <= mid:
        sorted_arr.append(arr[i])
        i += 1

    while j <= end:
        sorted_arr.append(arr[j])
        j += 1

    arr[start:end + 1] = sorted_arr


if __name__ == "__main__":
    arr = [1,6,4,2,3,5]

    print(f"before : {arr}")  # 정렬 전 리스트
    merge_sort(arr, 0, len(arr)-1)
    print(f"after : {merged_arr}")  # 정렬 후 리스트

시간 복잡도

입력 데이터의 크기가 N일 때,

알고리즘의 연산 횟수는 아래와 같다.

• 배열 분할 작업
  • 균등한 크기로 2개의 배열로 반복해서 나누기 때문에, log n번 반복한다.
• 배열 병합 작업
  • 더이상 나누어지지 않을 때까지 분할한 후, 다시 2개의 배열을 합치면서 정렬하는 과정이다.
  • 리스트의 크기가 1인 상태일 때, 크기가 1인 배열이 총 N개 있다.
  • 이 N개의 크기를 비교하면서 2개씩 합쳐진 배열을 만들기 때문에, N번 비교연산한다.
  • N/4 크기의 배열일 때도, 4개의 배열이 존재하기 때문에 N/4*4=N번 비교연산한다.
• 결과
  • 따라서 합병 정렬의 시간 복잡도는 O(N logN) 이다.