알고리즘 합병정렬(MergeSort) 파헤치기

안녕하세요

블레이즈 테크노트 

블레이즈 입니다. 

생각해보니, 

제가 여유를 좀 갖고 블로그 포스팅을 적는 날이 주로 일요일인 것 같아요. 

 

그래서 여러분들도 하루를 마무리하면서 공부도 한 술 해보시면 어떨까요..? 하하

 

 

지난 포스트에서 삽입 정렬을 다루었습니다. 

https://blazetechnote.tistory.com/37

알고리즘의 정의와 삽입정렬 InsertionSort

 

이번 포스트에서는 합병정렬 MergeSort를 다뤄보려고 합니다. 

 

머지소트는 대표적인 Divide & Conquer 방식의 코드입니다. 

하지만 이 Divide&Conquer 라는 이름은 다소 mistaking 할 수 있습니다. 

왜냐하면 이러한 구조는 마지막에 반드시 combine 과정이 수반되어야 하기 때문입니다. 

 

그래서 저는 Divide-Conquer-Combine 이라고 적어봅니다. 

 

 

 

기본적으로 MergeSort는 문제의 크기를 절반으로 줄여가면서 list의 원소가 1이 될 때까지 계속한다는 아이디어입니다. 

 

그림으로 표현하면 위와 같습니다. 

 

이를 코드로 나타내면 다음과 같습니다. 

 

 

 

Merge() 함수의 시간복잡도를 line-by-lined으로 나타내면 다음과 같습니다. 

 

이를 통해 Merge() 는 Big-Theta(n) 임을 증명했습니다. 

 

이를 바탕으로 합병정렬 전체의 시간복잡도를 나타내면 아래와 같이 Recurrence Relation의 형태로 나타납니다.

 

이러한 Recurrence Relation은 식이 재귀적으로 정의되어 있어서 풀기가 조금 복잡한데요, 

차후  Recurrence Relation의 해법을 다루도록 하겠습니다.