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

이번 절은 다중 병합과 치환 성택에 대한 내용이다.

이중 병합은 순서 있는 수열 두 개를 하나의 단일한 순서 있는 수열로 병합하는 공정이다.

이를 P개의 입력 연속열들을 하나의 출력 연속열로 결합하는 P중 병합으로 확장하는 것은 어렵지 않다.

 

각 연속열의 첫 레코드들 중 키가 제일 작은 것을 선택하고 출력으로 보내고 입력에서 제거하는 방법을 사용하면 된다.

이런 작업을 할 때 자료구조 중 힙을 사용하는게 유용할 수 있다.

 

그 이후에는 연속열에 대한 설명들이 나온다.

 

이후에는 일부 연속열은 오름차순이고 일부는 내림차순임을 요구하는 병합 패턴을 사용하는 응용을 볼 수 있다.