이 알고리즘 역시 이해는 어렵지 않다. 트리구조로 파악 후 하위트리들을 작은수를 앞에 놓는 식으로 차례차례 상위로 이동하면서 병합하는 방식이다. 그런데 이해는 쉽게 되는데 선뜻 코드가 바로 짜여지지 않는다. 아무래도 트리구조로 탐색, 이동해야 되니 이동방식에 대한 고민이 만만찮고 배열 갯수가 2의 제곱으로 나누어지지 않는 부분에 대한 처리도 신경써야 되기 때문일 것이다. 여기저기 참고하고, 손질 좀 하고 시간 좀 걸려 짜 놓은 소스를 보니 참 길고 루프문도 많이 사용됨을 볼 수 있었다. 사용된 지역변수가 11개나 된다. 원래 각 트리 단계별로 보통 버퍼에 결과를 저장한 후 다시 원본배열로 이를 복사하는 방식을 사용하기도 하지만 이를 개선하는 방법도 있다.(이재규 알고리즘 서적 참조) 어차피 버퍼와 원본배..