출처 : Unsplash

합병 정렬(merge sort)

분할 정복(divide-and-conquer) 알고리즘의 대표적인 예시인 합병 정렬에 대해서 알아 보자.

📌 목차

1. 설명
2. 구현
   a. 코드
   b. 결과

📌 설명

합병 정렬(merge sort):
주어진 배열을 더 이상 쪼갤 수 없을 때까지 데이터 크기의 절반으로 계속 나누어, 재귀적으로 정렬을 수행하면서 통합하는 정렬 알고리즘.

출처 : Wikipedia

분할정복 알고리즘에 맞게 3단계로 나누어 설명하면 아래와 같다.

• Divide

  • 주어진 배열을 데이터 크기($N$)의 절반 ($\frac{N}{2}$) 으로 나누어 2개의 부분 배열로 분할한다.
  • 이를 더 이상 쪼갤 수 없을 때까지(데이터 크기 1~2개의 부분 배열) 분할한다.

• Conquer

  • 나누어진 부분 배열에 대해서 재귀적으로 합병 정렬을 한다.
  • 단, 데이터 개수가 1개인 부분 배열은 이미 정렬된 상태로 간주한다.

• Combine

  • 정렬한 2개의 부분 배열을 통합하여 원래 크기의 정렬된 배열로 만든다.

📌 구현

코드

def merge(arr, low, high):
    temp = []
    mid = (low + high) // 2
    i, j = low, mid + 1

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

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

    while j <= high:
        temp.append(arr[j])
        j += 1

    for k in range(low, high + 1):
        arr[k] = temp[k - low]

    return arr


def merge_sort(arr, low, high):
    if (low >= high):
        return  # base case

    mid = (low + high) // 2

    merge_sort(arr, low, mid)
    merge_sort(arr, mid+1, high)

    sorted_array = merge(arr, low, high)

    return sorted_array


# test code
if __name__ == "__main__":
    unsorted_array = [5, 6, 4, 0, 2, 1, 7, 3, 8]
    print(f"unsorted array :\t {unsorted_array}")
    print(f"sorted array :\t\t {merge_sort(unsorted_array, 0, 8)}")

결과

unsorted array :	 [5, 6, 4, 0, 2, 1, 7, 3, 8]
sorted array :		 [0, 1, 2, 3, 4, 5, 6, 7, 8]