[Sorting Algorithms] Merge Sort (합병 정렬)

---

<모든 포스팅은 오름차순에 기반합니다.>

필기시험에서 나를 괴롭혔던 바로 그놈이다.

아직도 그때만 생각하면 이불킥중.

Merge Sort는 분할정복법, 재귀를 떠올리면 된다.

커~~다란 배열을 반씩 반씩 쪼개서 조각조각 정렬을 한 뒤 합치는 정렬법이다.

쉽게 말해 분할 - 정렬 - 병합 세 단계로 나뉜다.

Merge Sort에는 딱히 Target Index라고 칭할만한 대상이 없다.

일단 쪼개는게 우선, 그리고 이를 정렬하고 다시 병합하는 과정에서 Target Index가 필요하다.

결국, Merge Sort 구현의 핵심은 '병합'에 있다.

<1단계 : 분할>

기준은 크기(길이)가 1이면 Sorted 상태로 간주한다.

쪼개는 과정은 재귀호출로 해주면 되기 때문에 구현이 매우 쉽다.

[0]	[1]	[2]	[3]	[4]	[5]	[6]
5	3	1	7	11	9	4

Array's Size / 2 의 크기로 쪼갠다. ( Divide() )

[0]	[1]	[2]	[3]		[0]	[1]	[2]
5	3	1	7		11	9	4

2nd Divide();

[0]	[1]		[0]	[1]		[0]		[0]	[1]
5	3		1	7		11		9	4

3rd Divide();

[0]		[0]		[0]		[0]		[0]		[0]		[0]
5		3		1		7		11		9		4

이제 Size가 1인 상태까지 모두 분할이 완료됐다.

---

<2단계 : 정렬> 그리고 <3단계 : 병합>

3단계로 나눴지만, 사실상 2단계와 3단계는 동시에 이루어질 것이다.

Merge 하는 과정에서 Sort도 함께 이루어지기 때문이다.

물론 최종 정렬이 3단계인 병합 과정이라고 해야겠지만,

둘로 나뉘어진 배열의 원소를 서로 비교하려면 두 배열은 각각 정렬된 상태여야 한다.

잠시 예를 든다면,

[0]	[1]	[2]	[3]		[0]	[1]	[2]
5	3	1	7		11	9	4

1st Divide()로 이렇게 나뉘어있는 두 배열을 Merge Sort의 알고리즘대로 임시 정렬해보자.

양 배열의 0번째 인덱스끼리 비교해서 작은 수인 5를 새 배열에 우선해서 넣는다.

그 후 좌측 배열의 Index를 하나 이동해 3과 11을 비교해 작은 수인 3을 새 배열에 넣는다.

벌써부터 정렬이 불가능함을 알 수 있다.

배열에 5 - 3 - 1 - 7 순으로 입력될테니 말이다.

따라서 양측 배열은 각각 정렬된 상태로 만나야 한다.

그렇기때문에 분할과 정렬이 필요한것이다.

다시 본론으로 돌아와 정렬+병합 과정을 살펴보자.

Left		Right		Left		Right		[0]		Left		Right
5		3		1		7		11		9		4

2nd Divide()에서 분할되기 직전, 붙어있던 Index끼리, 즉 같은 색의 Index끼리 비교가 진행될 것이다.

여기서 중요한 점, Merge Sort는 정렬과정에서 '별도의 메모리 공간'이 필요하다.
두 Index를 합치기 위해선 새로운 배열이 등장해야 한다는 말이다.
이 때문에 메모리 공간 활용도 면에선 치명적인 단점을 드러낸다.

어쨌든, Left와 Right를 서로 비교해 더 작은 수부터 새로운 배열에 들어가게 된다.

Left		―	Right			Left	―	Right
3	5		1	7		11		4	9

그 결과 이렇게 2nd Divide() 상태로 배열이 합쳐지게 된다.

여기서 앞의 두 배열만을 예시로 병합해보자.

---

Left [0]	[1]		Right [0]	[1]
3	5		1	7

이 두 배열의 0번째 Index부터 서로 비교해 작은 수를 새 배열에 채워 넣을 것이다.

3 > 1 이므로 1을 넣는다.

1

---

Left [0]	[1]		[0]	Right [1]
3	5		1	7

Right의 Index를 한 칸 이동하고 3과 7을 비교한다.

3 < 7 이므로 3을 넣는다.

1

3

---

[0]	Left [1]		[0]	Right [1]
3	5		1	7

Left의 Index를 한 칸 이동하고 5과 7을 비교한다.

5 < 7 이므로 5을 넣는다.

1

3

5

7

그리고 7을 넣고 마무리한다.

---

이렇게 두 배열은 정렬이 완료된 상태에서 만난다.

[0]	[1]	[2]	[3]		[0]	[1]	[2]
1	3	5	7		4	9	11

그러면 다음 단계로 두 배열을 앞선 방법과 같이 새 배열에 순서대로 넣으면 정렬은 끝난다.

나누고 정렬하고 합치는 과정이 세분화되기 때문에 포스팅이 길어졌지만, 실제로 처리되는 과정이나

정렬 내용은 전혀 복잡하지 않다.

실제로도 현업에서 많이 쓰이는 방법이기도 하고, 공간적 낭비나 Quick, Heap에 성능으로 밀리는 점을 제외하면

아주 좋은 알고리즘이기 때문에 꼭 새겨둬야 한다.

<구현의 핵심>

- Merge Sort는 분할정복법, 재귀를 사용한다.

- 병합을 위한 별도의 메모리 공간이 필요하다.

- 나누는 것은 쉽다. 합치는 것이 관건이다.

- 배열을 최소 크기로 작게 쪼갠다. Size(Length) = 1.

- Left와 Right 배열의 원소간 대소비교를 통해 작은 수부터 새로운 배열에 집어넣는다.

- 모든 병합이 완료됨과 동시에 정렬이 끝난다.