def mergesort(S) 부분이 이해가 가지 않습니다.

Question

def mergesort(S)에서 리스트를 U와 V로 2분할 할 때, 즉, mergesort 재귀호출이 아닌 그냥 U = S[0:mid] V = S[mid:n]  이렇게 할 경우 왜 값이 다르게 나타나는지 모르겠습니다.

joonion · Answer

merge() 함수는 이미 정렬되어 있는 것을 합치도록 코드가 구성되어 있죠? 재귀 호출을 하지 않으면 정렬되지 않은 값이 merge 함수의 파라미터로 넘어가니까 정상동작을 할 수 없는 것입니다.

joonion · Answer

재귀 함수 호출에 익숙하지 않군요. 먼저, 팩토리얼 함수를 재귀적으로 구현해서 위에서 처럼 그림을 그려보세요. 다음, 피보나치 함수의 재귀적 호출 구조를 연구해 보세요. 그리고 나서 다시 돌아와서 mergesort()를 들여다 보세요. 그렇게 해야 이해가 될 겁니다. breakpoint를 찍을 줄 알면, breakpoint를 적극 활용해 보세요.

realbale · Answer

답변 감사합니다. 왜 재귀 호출을 해야하는지까지는 이해했습니다. 그런데 재귀 호출을 2번하다보니 제가 함수 실행 순서를 정확히 이해를 못 하고 있는 것 같습니다. 결론부터 말하자면 제가 생각하는 출력은   입니다. 이해가 가지 않아서 함수의 실행 순서를 제가 직접 그림을 그려 보았습니다(1번부터 7번까지). 어느 부분에서 잘못되었는지 지적해주시면 감사하겠습니다.