병합 정렬(Merge sort)

병합정렬

시간복잡도	공간복잡도
모든 값을 비교해야하므로 N 반복을 거듭할 때마다 반씩 줄어듦으로 log N O(N log N)	배열을 병합할 때 병합 결과를 담아놓을 배열이 필요함 O(N)

 

주어진 요소가 각 1개가 될 때까지 분할한 후 각 요소들을 병합하는 과정에서 비교하여 정렬하는 방식. 분할 정복과 재귀 용법을 이용하는 알고리즘.

 

[7, 4, 5, 1, 3]

 

예를 들어 이렇게 주어진 배열을 정렬한다고 해보자.

 

먼저 모든 요소가 1개가 될 때까지 반으로 쪼갠다. 전체 배열의 길이를 2로 나눈 후 소숫점과 나머지는 버리고 몫만 얻어서 배열을 반으로 나눈다.

len(input_array) // 2
=> [7, 4]   [5, 1, 3]
=> [7] [4]  [5] [1, 3]
=> [7] [4]  [5] [1] [3]

 

이후 두 개 요소를 비교해가며 병합한다

[7] [4]  [5] [1] [3]
=> [4, 7] [5] [1] [3]
=> [4, 7] [1, 5] [3]
=> [4, 7] [1, 3, 5]
=> [1, 3, 4, 5, 7]

1. 두 개의 배열에서 가장 앞의 값을 가져와 비교한 후 작은 값을 임시 배열에 넣는다.

2. 작은 값이 빠진 배열의 두번째 요소와 이전에 큰 값을 가졌던 배열의 첫번째 값을 다시 비교한다.

3. 두 배열중 하나의 배열에서 모든 값이 비교되어 임시배열에 들어갈 때까지 반복한다.

4. 두 배열 중 값이 남아있는 배열의 값은 비교 요소들 중 큰 값만 남은 것이기 때문에 임시배열의 뒤에 그대로 붙여주고 리턴한다.

 

이렇게 쪼개고 병합하는 과정을 재귀적으로 반복한다.

 

 

 

구현

def merge_sort(input_array):

    if len(input_array) < 2:
        return input_array

    mid = len(input_array) // 2

    low_arr = merge_sort(input_array[:mid])
    high_arr = merge_sort(input_array[mid:])

    merged_arr = []
    l = h = 0
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
        else:
            merged_arr.append(high_arr[h])
            h += 1
    merged_arr += low_arr[l:]
    merged_arr += high_arr[h:]

    return merged_arr

두 배열을 비교하는 while문에서는 배열 안의 값을 빼고 넣는 것보다 l, h의 임시 인덱스를 사용하여 효율적으로 비교한다.

 

다만 파이썬의 split은 매번 배열을 복사하여 반환하므로 메모리 사용효율이 떨어진다.

 

최적화

매번 split을 사용하여 새로운 배열을 복사하지 않고 인덱스 접근을 통해 원본 배열 내에서 정렬한다.

 

def merge_sort(input_arr):
    def sort(low, high):
        if high - low < 2:
            return

        mid = (low + high) // 2
        sort(low, mid)
        sort(mid, high)
        merge(low, mid, high)

    def merge(low, mid, high):
        temp = []
        l, h = low, mid

        while l < mid and h < high:
            if input_arr[l] < input_arr[h]:
                temp.append(input_arr[l])
                l += 1
            else:
                temp.append(input_arr[h])
                h += 1

        while l < mid:
            temp.append(input_arr[l])
            l += 1
        while h < high:
            temp.append(input_arr[h])
            h += 1

        for i in range(low, high):
            input_arr[i] = temp[i - low]

    return sort(0, len(input_arr))

 

 

 

참고

https://www.dalecoding.com/algorithms/merge--sort

병합 정렬 (Merge Sort) | 달레코딩