[알고리즘] 병합정렬을 그림으로 알아보자

 

 

📚 병합 정렬이란?

 

병합 정렬은 정렬할 배열을 더 이상 쪼개질 수 없는 상태까지 나눈 다음  합치면서 정렬을 하는 방법이다.

 

 

📋 병합 정렬 전체 과정

 

병합 정렬은 2가지 과정을 거친다.

정렬할 배열을 나누고(merge sort) -> 합친다(merge)

 

 

https://velog.io/@emily0_0/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Merge-Sort

 

 

📋 merge sort

 

병합 정렬은 더 이상 쪼개질 수 없는 상태 즉,

쪼개진 배열의 길이가 1이 될 때까지 나눈다.

왜냐하면 배열의 길이가 1이면 그 속에 무슨 숫자가 들어있는 정렬이 모두 완료된 상태이기 때문입니다.

 

시간복잡도를 계산해가면서 배우는 게 낫기 때문에

시간복잡도 관점에서 과정을 설명해드리겠습니다.

 

 

다음과 같은 배열을 정렬해봅시다.

처음 배열의 개수는 N 개라고 합시다.

 

   

그다음은 N인 배열을 반으로 나눕니다.

그러면 길이가 N/2개인 배열 2개가 나옵니다.

 

 

그다음은 N/2인 배열을 반으로 나눕니다.

그러면 길이가 N/4개인 배열 4개가 나옵니다.

 

 

 

그다음은 N/4인 배열을 반으로 나눕니다.

그러면 길이가 N/8개인 배열 8개가 나옵니다.

(앞의 예시는 N이 7이었으니 길이가 1인 7개의 배열로 나눕니다.)

 

 

우리는 여기서 규칙을 찾을 수 있습니다.

 

나누는 과정이 K번 이후에는  

N/(2^k)인 배열을 반으로 나누고,

그러면 길이가 N/(2^k)개인 배열 2^k개가 나온다는 겁니다.

 

 

N/(2^k) = 1 가 이 될 때까지 배열을 나누게 되니

N = 2^k 가 되고 log를 취해주면

log₂N = k 이 됩니다.

즉 logN = k 횟수를 시도하면 되는 것입니다.

 

 

즉 병합 정렬의 분할 과정의 시간복잡도는 O(logN)이 됩니다.

이 과정은 이진 탐색의 시간복잡도를 구할 때와 똑같으며 이진 탐색의 시간복잡도는 O(logN)입니다.

 

 

📋 merge 

 

나누는 것을 해결했으니 이제 합쳐봅시다.

 

 

완전히 다 쪼개진 상태에서

크기 N/4인 정렬된 부분 배열 4개로 만들기 위해

크기 N/7인 부분 배열 7개를 비교한다.

그러면 N/7 * 7 = N번 비교한다.

 

 

크기 N/2인 정렬된 부분 배열 2개를 만들기 위해

크기 N/4인 부분 배열 4개를 비교한다.

그러면 N/4 * 4 = N번 비교한다.

 

 

크기 N인 정렬된 부분 배열 1개를 만들기 위해

크기 N/2인 부분 배열 2개를 비교한다.

그러면 N/2 * 2 = N번 비교한다.

 

 

모든 단계에서 N만큼 비교한다

이 N번을 logN(분할과정에서 나누어진)만큼 비교한다.

 

즉 N * logN이 되어

병합 정렬의 시간복잡도는 총 O(NlogN)이 된다.

 

 

📝 병합 정렬 코드(feat : python)

 

array = [4, 1, 7, 5, 3, 2, 6]


def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left_array = merge_sort(array[:mid])
    right_array = merge_sort(array[mid:])
    return merge(left_array, right_array)


def merge(array1, array2):
    result = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):
        while array2_index < len(array2):
            result.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2):
        while array1_index < len(array1):
            result.append(array1[array1_index])
            array1_index += 1

    return result


print(merge_sort(array))