[Algorithms] Merge Sort (합병 정렬) 원리[Temp]

Merge Sort (합병 정렬) 원리

---

포스트 난이도: HOO_Middle

[Notice] 포스트 난이도에 대한 설명

---

 

# Merge Sort

 

전공자들이라면 Data Structure 수업 때 배웠던 대표적인 algorithms 중에 하나가 Merge sort이다.

한국말로 번역하면 합병 정렬이라고도 하는데 말 그대로 나눈 다음에 합쳐서 정렬이 이루어지는 특성을 가지고 있기에 Merge sort라고 부른다.

이번 포스트에서는 Merge sort에 대한 원리를 다시 살펴봄으로써 Divide and Conquer algoritms에 대해 알아보기 위한 기본기를 다져보도록 하자.

 

Merge sort에 대해서는 기본적으로 이해를 하고 있다고 가정하에 Merge sort에 대한 원리 부분으로 넘어가도록 하겠다.

우선 Merge sort를 왜 사용하는가?라고 한다면 무작정 sorting하는 것보다 빠르기 때문이다.

따라서 Time complexity가 다른 sorting 방법과 비교하여 얼마나 빠른지에 대한 증명 과정을 이전 수업이나 공부하면서 배웠을 것이다.

필자가 빠르다는 걸 언급한 이유는 Merge sort가 어떤 원리로 작동되는지 살펴보기 위해서이다.

아래는 Merge sort의 조건이다.

if n =1 일 경우에는 T(n) = 0이고

if otherwise 일 경우에는 T(n) = 2T(n/2) + n이 성립된다.

 

Merge sort의 특징은 나눠서 정렬하고 합쳐주는 특징을 가지고 있는데 1인 경우에는 알고리즘이 수행할 수 없으니 결과값이 0이 나온다.

반면에 다른 cases들의 경우에는 Merge sort가 수행이 가능하다.

2T(n/2)는 sorting both halves를 하는 부분이며, n은 merging이 이루어지는 부분이다.

결과적으로 n의 갯수에 따라 해당 조건이 충족되고 나면 결과적으로 T(n) = nlog2 n이 나온다.

---

# Merge  sort 원리 예제

Merge sort의 원리를 이해하기 위해서 그림 예제를 살펴보도록 하자.

알고리즘을 쉽게 이해하기 위해서는 직접 그려보며 해보는 것이 가장 좋다.

그래야지만 coding 과정에서 머릿속으로 알고리즘에 대한 시각화를 통해 응용이 가능하다.

 

---

# In conclusion, 3줄 요약

1.

2.

3.