[알고리즘] 병합정렬 알고리즘 | Merge Sort | C++코드 해석

분할정복(Divide and Conquer) 알고리즘을 공부하고있습니다.

병합정렬을 이해해보겠습니다, 우선은 코드는 이렇게 생겼습니다

코드를 이해하기 쉽도록 병합정렬의 개념과 예시그림을 설명하겠습니다!

 

병합정렬은 분할과 정렬로 나눌수있습니다.

먼저 처음과 끝의 중간에서 두 개로 분할합니다.

이후 분할된 블록들을 계속해서 최소단위까지 분할해줍니다.

 

8개의 수열을 분할하는 과정을 예로 들면, 

이런 식이 됩니다.

코드를 보면 이에 재귀함수를 이용하였는데요, 빨간색 숫자는 재귀함수에 따라 분할이 되는 순서입니다.

재귀함수가 머리아프신분들은 저 순서를 보시면 직관적으로 바로 이해가 되실 거에요! 

 

분할이 끝났으면 5번에서 정렬&병합 한번, 8번에서 한번,

8번 병합이끝나고 6번에 돌아와서 한번, 6번에서 끝나고 2번에서 한번... 이런식으로 이루어집니다.

 

5번 분할이 끝난후 정렬&병합되는 과정은

이렇습니다. i는 왼쪽 수열, j는 오른쪽 수열의 포인터를 담당한다고 생각하면됩니다.

한칸짜리로는 각각 i와 j가 어떤 역할을 하는지 바로 알기 어려움으로 

 

8번 병합이 끝난후 6번에서 이루어지는 정렬&병합을 살펴보겠습니다

코드에 써있듯이, 왼쪽블럭과 오른쪽블럭을 비교하며 작은쪽이 임시배열인 B에 차례차례 들어가게됩니다.

B에 채워넣은다음에는 채워넣어진 쪽의 포인터가 한칸 전진하게됩니다. 

 

이러한 전체적인 과정을 움짤로 보자면,

출처: https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#s-2.2.1

 

이런식이 됩니다 ;)