[자료구조] 6-2. 합병(merge) 정렬

O(n²) 정렬 알고리즘의 핵심은 이동이든 교환이든 원소들을 하나씩 비교하는 것이었다. O(n log n)정렬은 이것을 지양하는 알고리즘이다. 분할 정복 방식을 추구하는 합병 정렬(머지 정렬)과 쾌속 정렬(퀵 정렬)이 있고 트리 구조를 이용하는 힙 정렬이 있다.

분할 정복은 적절한 크기의 부분 집합으로 분할한 다음 문제를 해결하고 그 부분 집합의 해를 결합해서 최종값을 내는 과정을 거친다.

위의 리스트를 아래로 정렬해보자.

먼저, 주어진 리스트를 반으로 분할한다.

각각의 부분 집합을 정렬하는 정복 단계를 수행한다.

정렬한 두 개의 집합을 합친다.

정복은 그 안에서 또 분할, 정복, 결합의 과정을 거친다. 더 이상 쪼개지지 않을 만큼 작은 걸 만나서 예외처리를 하기 전까지는 재귀적으로 연산을 수행한다.

정복은 반드시 이 3가지 구성 요소를 가져야 한다.

1. 같은 형식으로 문제를 풀어야 한다. 정복이 분할-정복-결합을 반복하는 것이라면, 그 과정을 똑같이 반복해야 한다.

2. 분할할 때마다 문제의 크기가 줄어들어야 한다. 그렇지 않으면 오류다.

3. 예외처리를 해야 한다.

합병 정렬은 폰 노이만이 제안한 알고리즘이다. 여기 L과 R 두 정렬된 리스트를 M으로 합병하려고 한다. 그러면 M도 정렬된 리스트여야 하니까 M의 첫 번째 자리에는 가장 작은 수가 와야 한다. 그럼 L의 가장 작은 수와 R의 가장 작은 수를 비교하면 된다.

L과 R의 최소값 두 개만 비교하면 된다. 즉, 가장 작은 값은 L[0] 또는 R[0]이므로 시간 복잡도는 O(1)이다.

두 번째 또한 두 리스트에 있는 숫자 중 제일 작은 수를 넣는다. 단, L은 원래 리스트를 다 따져야 하지만, R은 가장 작은 수가 빠졌으므로 그 다음 나오는 수 중에서 가장 작은 수를 찾으면 된다. 5와 19 중 5가 더 작으므로 M[1]=5가 된다.

계속 반복하면 두 리스트는 합병된다.

모든 과정에서 연산은 2개의 수를 비교했으므로 O(1)이다. 리스트가 아무리 길어도 맨 앞에 있는 수만 비교하면 되니까 상수 시간이 가능한 것이다. 그러한 연산을 n번 반복했으므로 O(n)만큼의 연산을 하면 합병이 완료 된다.

이 그림은 합병 정렬의 핵심을 설명한다. 여기엔 정렬되지 않은 8개의 숫자가 있다.

이전에 배운 O(n²) 정렬 알고리즘에서는 8개의 원소를 가진 정렬되지 않은 리스트 1개에 대해 8개 원소를 비교하여 정렬한다.

합병 정렬은 각각을 1개의 원소만 가진 정렬된 리스트 8개로 본다.

그러면 정렬되지 않은 리스트를 정렬된 리스트로 만들기 위해 정렬 알고리즘이 필요했던 상황에서 벗어나, 이제는 합병만 하면 된다. 폰 노이만은 정렬이 아니라 합병을 통해서 정렬하는 방법을 제안한 것이다.

합병의 1단계는 각 리스트가 2개씩 합병되는 것이다. 이제 2개의 원소를 가진 정렬된 리스트 4개가 되었다.

또 다시 2개의 원소를 가진 리스트끼리 합병한다. 4개의 원소를 가진 2개의 정렬된 리스트가 나왔다.

마지막으로, 하나로 합병이 되어 8개의 원소를 가진 정렬된 리스트 1개가 된다.

시간 복잡도를 따져보자. 맨 처음에 n개를 합병하는 데에 O(n)이 걸린다고 했었다. 맨 처음 단계는 2개를 합병 했으므로 O(2)이고, 4개가 있으니 O(8)이 걸린다.

이 또한 O(4)가 2번 되니까 O(8)이 걸린다.

마지막 단계는 8개의 원소니까 O(8)이다.

다시 말해서 각각 O(n)이 걸린다고 말할 수 있다. 그런데 이 과정은 log n번만 수행하면 된다. 따라서 O(n)을 O(log n)만큼 합치는 데 걸리는 시간은 O(n log n)이 된다. 그래서 합병 정렬은 기존의 정렬 알고리즘보다 훨씬 효율적이다.

합병 정렬도 분할 정복 알고리즘이기 때문에 위의 과정을 거친다.

분할 과정은 반으로 쪼갤 때 중간 인덱스만 찾으면 되므로 한 번에 할 수 있다. 반으로 쪼개는 작업을 계속 반복하는데 이 시간을 쭉 계산하면 총 n-1번 분할하므로 O(n)번 분할한다고 할 수 있다.

정복은 O(1)이면 끝난다.

마지막으로 결합하는 데는 O(n log n)의 시간이 걸린다. 따라서 합병 정렬 알고리즘은 총 O(n log n)이 걸리는 알고리즘이다.

합병 정렬 알고리즘은 정복이 정복을 부르는 구조이므로 재귀 호출이 구현되어야 한다. 또한, 데이터를 효율적으로 관리하기 위해 시작과 종료 인덱스를 매개변수로 이용한다. 원소가 하나만 남은 예외 경우에는 시작과 끝 인덱스가 같음을 이용해서 표현한다.

1. arr이라는 배열에 대해 정렬을 수행하기 위해 0부터 n-1까지 즉, 첫번째 원소부터 마지막 원소까지 정렬 하겠다고 호출한다.

2. 시작과 종료 인덱스를 매개변수로 받는데 이때 둘이 같으면 원소가 1개인 경우이므로 예외처리를 해준다.

3. 분할하는 과정은 n/2을 중간값으로 해서 시작부터 n/2까지, 그리고 다음 원소부터 마지막 원소까지 각각 merge_sort 해주면 된다.

merge 함수 쪽은 꽤 복잡하다.

예시를 보자. 시작과 종료 인덱스인 0과 7일 매개변수로 보낸다. mid값은 3.5이므로 integer 변환으로 3이 된다.

따라서 0부터 3까지와 4부터 7까지의 2개 배열로 나뉜다. 그중에서 첫번째 배열에 대해 합병 정렬을 수행한다. merge_sort(0,3)

마찬가지로 mid를 구해서 쪼갠다.

드디어 예외의 경우를 만났다. 

정렬이 끝이라고 판단하고 끝이라고 리턴한다.

이제 마지막의 두 배열을 합칠 단계다.

merge(0,0,1,1)을 수행해 합쳐졌다.

이제 다시 2에서 3까지 합병 정렬을 수행한다.

계속 나누고

예외 처리로 정렬을 끝낸다.

처음 2개의 정렬이 끝났다.

merge(0,1,2,3)으로 합병한다.

0에서부터 3까지의 합병 정렬이 마무리되었다.

계속 반복하면 이렇게 완료된다. 굉장히 길고 복잡한 연산이다. 하지만 시스템에서 스택으로 구현을 해주기 때문에 걱정하지 않아도 된다.

정리하자면 시간 복잡도는 이렇게 된다. 점화식으로 표현하자면 n개의 데이터에 대해서 수행하는 시간은, n/2개짜리를 2개 수행한 다음 예외처리나 분할을 해서 +1이 된다.