병합정렬(merge sort) 알아보고 구현하기

Merge sort?

 

 병합정렬, 병합의 뜻은 2개가 하나로 합쳐짐을 의미한다. 즉 정렬되지 않은 리스트를 하나로 합치며 정렬하는 정렬알고리즘이다. 그리고 당연히 2개의 배열을 합치려면, 처음에 주어진 배열을 쪼개는 과정도 필요하다.

 

병합정렬은 크게 두 가지의 과정이 필요하다

 

나누기

 

합치며 정렬하기

 

 

8칸의 배열이 있다고 가정을 하자

그리고 우리는 이것을 2개씩 나눈다. 그리고 또 나눠진 2개의 배열을 각각 2개로 계속 나눠서 결국 하나씩 남게 한다.

 

그리고 이 남은 8개의 값을 나누기 직전에 같은 배열이였던 값과 비교해서 정렬을 시켜서 합친다.

그리고 이제 남은 4개의 배열을 또 합쳐야하는데 어떻게 합칠까?

위에서 합치며 정렬한다고 했다. 그 과정을 봐보자.

 

[3,7]과 [1,6]을 합치는 과정을 한번 보도록 하자. 당연히 위에서 정렬을 했기 때문에 배열은 정렬이 되있어야 한다.

그렇게 2개의 배열을 비교를 한다. 각각 배열 가장 앞의 인덱스에 있는 값을 비교한다.

1과 3중 1이 더 작기 때문에 1을 새 배열의 맨 앞에 배치한다.

그 다음 3과 6을 비교하면 3이 더 작으므로 그 다음에 배치.

6과 7을 비교하면 6이 더 작으므로 그 다음에 배치.

남은 7을 가장 마지막에 배치.

 

이런 식으로 2개의 배열을 합치며 정렬을 한다.

 

사실 위에 1개 씩 있는 값들을 정렬하며 합칠때도 이런 과정이지만, 단 한개뿐인 값들로 하다보니 설명하기 애매해서 이 부분에서 설명했다.

이후에도 이런식으로 다시 합쳐주면 된다.

병합정렬의 소요시간은 O(nlogn)으로 상당히 빠른 축의 정렬이다.

 

파이썬으로 구현한 병합정렬을 보자.

def merge(left, right):
    result_arr = []
    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0] <= right[0]:
                result_arr.append(left[0])
                left = left[1:]
            else:
                result_arr.append(right[0])
                right = right[1:]
        elif len(left) > 0:
            result_arr.append(left[0])
            left = left[1:]
        elif len(right) > 0:
            result_arr.append(right[0])
            right = right[1:]
    return result_arr

def merge_sort(arr):
    if len(arr) < 2:
        return arr

    mid = len(arr)//2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)


print(merge_sort([7,3,1,6,2,5,8,4]))