#5-4-3 The Art of Computer Programming - 정렬과 검색

이번 절은 중첩 병합에 대한 내용이다.

이것은 지난 절에 나왔던 다중 페이즈보다 먼저 발견되었다.

 

다중 페이즈 병합과 같이 중첩 병합도 연속열들을 테이프들에 정말 배분하는 것으로 시작하나

자료 전부에 대한 전체적인 패스를 가지고 작업한다.

마지막 복사 연산이 불필요하므로 생각이 가능한 특징이 있다.

 

병합 연산의 급격한 변화를 회피할 수 있는 것이 장점이다.

중첩 병합은 다중 페이즈에 비해 어렵지만 주목할만한 공식들이 존재한다.

 

균형 병합과 다중페이즈 병합의 조합도 연구한 결과가 있다고 한다.