CH10-2 복잡하지만 효율적인 정렬 알고리즘(5)

10-2. 복잡하지만 효율적인 정렬 알고리즘 ⑤

병합정렬을 계속 알아보자.

일단 MergeSort에서 봐야하는 큰 골격을 보자.

우선 mid는 left와 right를 더해서 2로 나눈다. 중간지점의 인덱스를 구한다. 이때 mid는 int형임

재귀적으로 사고하려면… 이런 가정이 있어야 한다.

함수의 재귀적 호출과정을 일일이 따라가지 말고, 첫 재귀호출에서 0에서 3까지, 4에서 7까지 정렬이 된다고 가정.

즉 1,4,2,7,3,5,9,0이… 아래의 단계로 일단 정렬이 된다고 가정.

정렬된 왼쪽, 오른쪽 영역을 그냥 합치는가?

아니다 이런 결과가 나와야한다.

어떻게 해야하나?

데이터를 하나하나까지 나누고 정렬해야 한다.

다시 말하자면… 처음의 단계에서 MergeSort가 한번 실행되면, 이렇게 두 단계로 나눠진다. 그리고 병합의 과정인 MergeTwoArray가 실행되어야 한다. 물론 이 단계에서 실제로 MergeTwoArray 가 실행되는건 아니고, 다시 분할의 과정을 거친다.(즉 실행되어야 하지만.. 재귀적 호출이 계속 이어지기 때문에 실제로 실행되지 않고 축적된다고 표현함

• 함수의 재귀적 호출에서 축적된다는 비유는 처음듣는데.. 굉장히 유용한 비유같다. 모든 함수의 호출관계를 일일이 추적하는게 아니라, 각각의 재귀적 호출 단계를 단계처럼 이해할 수 있게 때문임. 즉 위에서는 <분할-MergeTwoArray 축척>을 하나의 재귀호출 단계로 이해하면 편해보인다!