합병 정렬 (Merge Sort)

합병 정렬은 전형적인 Divide and Conquer 알고리즘이다.

합병 정렬이란?

합병 정렬(Merge sort)는 정렬 알고리즘으로, 주어진 배열을 두 개의 배열로 계속 분할한 뒤, 분할한 배열을 합치면서 정렬한다. 배열을 분할하는 과정에서 시간 복잡도 O(logN), 합치는 과정에서 O(N)을 가지므로 총 O(NlogN)의 시간 복잡도를 가진다. Quick sort, Heap sort처럼 시간 복잡도가 O(NlogN)이지만, 정렬을 위한 배열을 하나 더 생성하기 때문에 메모리를 더 많이 차지한다는 단점이 있다. 

 

원리

배열 [4, 3, 2, 1]이 있고, 오름 차순으로 정렬한다고 해 보자.

Merge sort는 분할을 먼저 수행하는데, 더 이상 나눠지지 않을 때까지 배열을 나눈다.

0: [4, 3, 2, 1]

1: [4, 3] [2, 1]

2: [4] [3] [2] [1]

 

분할이 완료됐으면 이번엔 새로운 배열에 합치는 과정에서 정렬한다.

합칠 때는 작은 숫자가 앞에 오도록 각 배열의 가장 작은 값을 비교하여 배열에 추가한다.

0: [4] [3] [2] [1]

1: [3, 4] [1, 2]

2: [1, 2, 3, 4]

 

만약 위의 과정 1에서 [2, 3] [1, 4]로 분할 되었다면, 아래 과정에 따라 합쳐진다.

1. [2, 3] 배열의 첫번째 인덱스와 [1, 4] 배열의 첫번째 인덱스를 비교한다. 

2. [1, 4] 배열의 첫번째 인덱스가 더 작으므로 먼저 배열에 추가한다.

3. [2, 3] 배열의 첫번째 인덱스와 [1, 4] 배열의 두번째 인덱스를 비교한다.

4. [2, 3] 배열의 첫번째 인덱스가 더 작으므로 먼저 배열에 추가한다.

5. [2, 3] 배열의 두번째 인덱스와 [1, 4] 배열의 두번째 인덱스를 비교한다.

6. [2, 3] 배열의 두번째 인덱스가 더 작으므로 먼저 배열에 추가한다.

7. [1, 4] 배열의 두번째 인덱스가 남았으니 마지막으로 배열에 추가한다.

 

다소 복잡해 보이지만 같은 로직을 반복하고 있는 것을 볼 수 있다.

1. 각 배열끼리 비교할 인덱스 i, j를 정한다.

2. 비교 후 더 작은 값을 배열에 추가하고, 해당 배열의 인덱스를 1 증가시킨다. (반복)

3. 인덱스 i, j 값이 배열의 길이와 같으면 반복을 종료한다.

 

구현

Merge sort는 재귀로 구현이 가능하지만, 비재귀로 푸는 것보다 시간이 더 걸린다는 단점이 있다. 

먼저 재귀로 구현해 보고, 익숙해지면 비재귀로 푸는 것이 좋을 것 같다.

 

Python Non-recursive

Python으로 비재귀 Merge sort를 구현해 보았다. 배열 길이가 홀수일 경우 마지막 배열은 합병 연산에 들어가지 않고 통째로 배열에 추가하는 기능을 넣었다.

- 인자로 배열 크기 n, 배열 arr를 받는다. arr에는 숫자가 문자로 저장되어 있다.

- 배열은 기본적으로 1개씩 분할되어 있다고 가정했다.

- 첫번째 반복문은 분할할 크기를 지정하는 것이고, 1부터 2, 4, 6, 8 ...n 까지 순회한다. 1 이외에는 분할 크기가 짝수가 되어야 하기 때문이다.

- 분할 범위를 i라고 하면, 검사를 시작할 인덱스를 si라고 한 후 배열 2개씩 비교하면서 정렬한다.

- si가 0이면 검사할 배열은 각각 [0:i], [0+i:i+i] 범위이다.

- 첫번째 배열은 항상 존재하지만, 전체 배열의 길이가 홀수일 경우 마지막 검사때 두번째 배열은 존재하지 않는다.

- 따라서 두번째 배열의 시작 인덱스가 전체 배열의 길이를 초과하면 합병 연산을 하지 않고 바로 배열에 추가한다.

- 각 배열의 값을 추가할 때 인덱스 값을 증가시킨다.

- 인덱스 값 - si(시작 인덱스)가 분할 크기보다 같거나 크면 배열에 추가하지 않는다.

def solution(n, arr):
    answer = 0
    merge = arr
    for i in range(1, n+1, 2): # i: 분할할 크기
        if i!= 1:
            i -= 1
        si = 0  # 인덱스
        while si < n:
            # 분할 범위 단위로 정렬
            index1 = si
            index2 = si+i
            m = []
            # index2가 배열 길이를 초과했을 경우(index1+i이 배열 끝일 경우)
            if index2 >= n:
                index2 = si
            while index1-si < i or index2-si-i < i:
                if index2 == si:
                    m = merge[si:]
                    break
                if index1-si >= i:
                    if index2 >= n:
                        break
                    m.append(merge[index2])
                    index2+=1
                    continue
                elif index2-si-i >= i or index2 >= n:
                    m.append(merge[index1])
                    index1+=1
                    continue
                if int(merge[index1]) < int(merge[index2]):
                    m.append(merge[index1])
                    index1+=1
                else:
                    m.append(merge[index2])
                    index2+=1
            merge = merge[:si] + m + merge[si+(i*2):]
            si += i*2
    return merge