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

이번 절은 병합에 의한 정렬에 대한 내용이다.

 

병합 혹은 취합은 둘 이상의 순서 있는 파일들을 하나의 순서 있는 파일로 합치는 것을 의미한다.

예를 들어, 8, 10, 19와 1, 5, 20 파일을 병합하면 1, 5, 8, 10, 19, 20의 파일이 되는 것을 병합이라 한다.

 

병합 알고리즘의 총 작업량은 본질적으로 m(나눈 수), n(수행한 수)에 비례한다.

그러므로 병합이 정렬보다 간단한 문제라고 할 수 있고, 정렬 문제를 병합 문제로 간소화가 가능하다.

정렬된 파일에 새 원소를 삽입하는 것은 n = 1인 특별한 경우의 병합이라 할 수 있다.

만일 삽입 공정의 속도를 높이고 싶으면 한 번에 여러 개의 항목들을 일괄적으로 삽입하는 방법이 있다.

 

결론적으로 내부 병합을 수행하는 경우에는 연결된 메모리 기법이 순차 할당보다 확실히 우월하다.

메모리 공간도 덜 소비하고 실행 속도도 10~20%가 빠르다.