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

이번 절은 외부 기수 정렬에 대한 내용이다.

 

이전 절들은 병합을 통한 테이프 정렬 공정을 논의했다.

이번에는 또 다른 정렬 방법을 소개한다. 대부분이 본질적으로 병합의 반대이다.

 

모든 병합 패턴은 각각 하나의 배분 패턴에 대응하며, 모든 배분 패턴은 각각 하나의 병합 패턴에 대응하도록 구성한다.

후방 읽기 방법에 대해서도 소개한다.

 

기수 정렬이 병합보다 우월한가에 대해서는

보통 기수 정렬이 병합 정렬보다는 열등하다고 한다.

치환 선택 기법이 병합 정렬에 결정적인 장점을 제공하기 때문이다.

한 번에 하나의 메모리 적재량보다 많은 레코드들을 내부 정렬로 정렬할 수 있도록

기수 정렬들을 배치하는 명백한 방법은 없다고 한다.

실제 진동 기수 정렬은 하나의 메모리 적재량보다 다소 작은 부분 파일들을 만들어 내는 경우가 많기 때문이다.

 

그러나 외부 기수 정렬이 바란직한 경우도 존재하는데,

파일이 긴 경우에는 안정적 기수 정렬이 가능하다고 한다.

기수 정렬은 알고리즘의 내부 루프가 복잡한 분기를 피하기 때문에 고속 컴퓨터들에서는 병합보다 우월하다.