합병정렬

 

제로초님의 블로그를 보면서 공부했다.

https://www.zerocho.com/category/Algorithm/post/57ee1fc107c0b40015045cb4

(Algorithm) 합병(머지, 병합) 정렬

 

개념은 어렵게 느껴지지 않았다.

 

정렬을 해야 하는 배열이 있고,

걔네들을 재귀적으로 원소 단위까지 쪼갠 다음에, 원소와 원소끼리 비교하며 정렬하는 방식이었다.

내가 헷갈렸던 부분은,

 

mergeSort 안에 return 값으로 merge(mergeSort(xxx), mergeSort(xxx))를 할당하는 부분이었다.

 

재귀적으로 mergeSort가 원소 단위까지 특정 배열을 쪼개는 것은 이해를 했다.

하지만, 쪼갠 다음에

합쳐진 배열끼리 다시 merge 하는 과정이 이해가지 않았다.

 

직접 종이와 펜으로 로직을 줄 그어가며, 마치 내가 콘솔이 된듯양 뜯어봤다.

 

문제점을 알게 되었다.

 

 

return 값으로 merge를 무시하고 사고 했던 것이었다. 

 

merge가 계속 누적되어서, mergeSort가 탈출 조건이 발동할 때까지, 따라 붙어야 하는데

중간에 merge를 빼고 생각했던 것이다.