알고리즘 | 합병 정렬 (Merge sort)과 분할정복알고리즘 | 코드 설명

---

합병 정렬 (Merge sort)이란?

분할정복알고리즘 중 하나입니다. 일단 분할정복법이 뭔지 먼저 설명하는 게 좋을 듯합니다.

 

---

분할정복 (Divide and Conquer)

분할정복은 다음의 3단계로 이루어집니다.

1. Divide --- 문제를 subproblem으로 나눕니다.

2. Conquer --- 그 subproblem을 재귀적으로 주루룩 정복합니다. 이때 Base case까지 다다르게 됩니다. Base case란, subproblem이 충분히 작으면 그냥 아주 쉽게, 거의 그 자체 풀리는 수준의 케이스입니다.

3. Combine --- 2단계에서 subproblem들을 정복해 해답을 얻었습니다. 이 답들을 Combine해서 맨 처음의 original problem의 해답으로 얻어냅니다. 

 

이것이 Divide and Conquer, 분할정복법의 단계입니다. 

이름에서 느껴지듯이, 문제를 분할해서 정복하는 것이죠

 

+ 참고로 앞서 공부한 insertion sort는 분할해서 정복하는 것이 아니었죠, 재귀적 호출도 없었고요. 이거는 Incremental method입니다. incremental한 진행을 보였었죠.

 

---

합병정렬 (Merge Sort)

이제 분할정복법을 이해했으니까 분할정복 개념이 사용되는 정렬방식 중에서 "Merge Sort"를 봅시다!

Merge sort는 분할정복이 사용된 정렬방식이기 때문에, Merge sort역시 3단계로 볼 수 있습니다. 

 

1. Divide --- Input으로 들어온 배열A을 뚝 잘라 subarray 2개로 나눕니다. 

2. Conquer --- 나눠진 subarray를 '재귀적 방법'을 이용하여 정렬되도록 합니다. 재귀호출했기 때문에 subarray는 또 계속해서 subarray로 나눠지고, 충분히 작아진(base case) subarray들부터 '정렬'되겠죠?

3. Combine --- 작은 subarray는 정렬된 상태입니다. 이제 이렇게 정렬된 조각조각 subarray들을 Merge합니다. 계속 merge(합병과 재정렬)해가면서 최종적으로는 배열A는 정렬된 상태가 됩니다. 

 

 

의사코드

그럼 이제, Merge Sort의 구조를 의사코드로 확인해봅시다. 

 

MERGE-SORT(A,p,r)
	if p<r
    	then q <- ⌊(p+r)/2⌋
        MERGE-SORT(A,p,q)
        MERGE-SORT(A,q+1,r)
        MERGE(A,p,q,r)

 

상세 과정은 제외하고 단지 구조를 보기 위해 작성된 코드입니다.

 

일단 input으로 들어온 배열A의 p번째~r번째 값들이 정렬 대상입니다. 

p번째~r번째 값들을 분할정복할 것이기 때문에, p~r을 계속해서 반으로 뚝뚝 잘라가게 됩니다. 

언제까지 자르냐? p<r를 만족하지 않을 때까지 입니다. 

 

재귀함수에서 가장 중요한 것은 이렇게 '멈추는 조건을 판단'하는 것입니다. 즉, base-case에 다다르는 때는 언제인가?라는 조건을 판단하는 것이죠. base-case에 다다르면 이제 그만 재귀과정을 멈추고 문제를 처리하여 돌아가야하기 때문에 이 p<r이라는 조건은 중요합니다.

 

아무튼 이 조건 하에서 MERGE-SORT(A,p,q)와 MERGE-SORT(A,q+1,r)이라는 재귀호출이 진행됩니다. 즉, 두개로 쪼갠 subarray에 대해 또 같은 과정으로 MERGE-SORT를 각각 시키는 것이죠. 깊게 생각할 필요 없습니다. 알아서 처리할 거예요.

 

그리고 맨 마지막으로, 이제 조각조각 나눈 subarray들을 합병정렬(Merge)해야 합니다. 이 부분, 합병정렬하는 이 MERGE 부분은 이제부터 자세히 보겠습니다. 지금 간단히 말하자면, "이미 정렬된 subarray" 두개를 이제 "합병"하고, 합병한 것을 즉석에서 "정렬"하는 처리를 하게 됩니다.  

 

---

합병정렬(MERGE)의 방법 고민

이제, 이미 재귀과정 후 정렬되어 올라온 subarray 두개를 다시 하나로 합병하여 정렬하는 방법을 생각해야 합니다. 

아래 그림과 같은 고민입니다.

 

subarray M과 N은 정렬된 상태로 올라왔습니다. 그리고 이 둘을 합쳐 정렬하여 더 상위단계로 가게 됩니다. 그럼 이 subarray들을 어떻게 합치고 어떻게 재정렬해야 할까요? 즉, MERGE 과정은 어떻게 진행될까요?

 

다음과 같이 진행됩니다.

MERGE함수를 의사 코드로 확인해봅시다.

MERGE(A,p,q,r)
	n1 <- q-p+1
    n2 <- r-q    //n1과 n2는 subarray의 길이가 됩니다.
    //subarray를 따로 담아둘 여분의 배열 2개 L,R을 만들어둡니다.
    Create arrays L[1 ... n1+1] and R[1 ... n2 + 1]
    //배열 L, R에 subarray를 나눠담는 과정
    for i <- 1 to n1
    	do L[i] <- A[p+i-1]
    for j <- 1 to n2
    	do R[j] <- A[q+j]
    //L, R의 맨 끝에 추가로 infinity를 추가합니다. (배열의 끝이라는 처리를 위해)
    L[n1+1] <- ∞
    R[n2+1] <- ∞
    //i,j는 각각 L,R배열에서 순서표시용으로 사용됩니다.
    i <- 1
    j <- 1
    //k는 배열A에서 재정렬시 순서 표시용으로 사용됩니다.
    for k <- p to r
    	do  if L[i] ≤ R[j]
        	then A[k] <- L[i]
            	i <- i+1
            else A[k] <- R[j]
            	j <- j+1

 

Merge과정 중에 subarray를 담아두는 배열 L, R를 따로 만들고 있습니다. 왜 L, R라는 여분공간이 필요할까요? 여분 배열 한개든 두개든 여분공간을 이용하지 않고 A안에서 해결할 수는 없을까요? 네 그러면 수들이 덮어써지는 문제가 일어납니다. 그래서 여분공간에 따로 수들을 담아두는 것입니다. 

 

사실 이렇게 여분의 공간을 만든다는 것은 Merge sort의 단점이기도 합니다. size가 작을 때는 상관이 없겠지만, size가 커진다면 메모리 차원에서 단점이 됩니다. 이러한 단점을 극복한 Quick sort라는 정렬방식이 있는데요, 나중에 공부해보도록 합시다. 

 

 

 

Merge sort는 어렵지 않아 쉽게 이해하겠지만..

그래도 위 알고리즘을 차근차근 해설한 영상을 첨부하겠습니다. 

 

 

다음 시간에는 Merge Sort의 시간복잡도를 공부해봅시다. 

https://splendidlolli.tistory.com/366

알고리즘 | 합병정렬(Merge Sort) 시간복잡도 - 확실하게 이해가 안가면 보세요