정렬 합병 #1. 대체 선택

정렬되지 않은 데이터를 정렬시키면서 하나의 파일에 합병하기 위해 대체선택으로 Run^[각주:1]을 생성해야한다.

▣ 대체선택의 런 생성 방법
1. 버퍼에 입력 파일로부터 m개의 레코드를 읽어와서 첫 번째 런을 생성한다.
2. 버퍼에서 키 값이 가장 작은 레코드를 선택하여 출력한다.
3. 입력 파일로부터 다음 레코드를 읽어와서 출력된 레코드와 대체시킨다.
   이 때 만일 읽어온 키 값이 출력된 키 값보다 작으면 읽어온 키 값에 "동결(Frozen)" 표시.
   동결된 레코드는 단계②에서 제외된다.
   아직 동결되지 않은 레코드가 있으면 단계②로 되돌아간다.
4. 동결된 레코드들을 모두 해제하고 단계②로 돌아가 새로운 런을 생성한다.

replacementSelection()     // 대체선택 알고리즘
     // m               : 버퍼에 들어가는 레코드 수
     // Buffer[]       : 버퍼 - 레코드 배열
     // written[]     : 해당 버퍼 레코드가 출력되었는지를 나타내는 플래그 배열
     // frozen[]      : 해당 버퍼 레코드가 동결되었는지를 나타내는 플래그 배열
     // lastkey        : 마지막으로 런에 출력된 레코드 키 값
     // input           : 입력 파일
     for( i=0; i<m; i++)
          written[i] = TRUE;
     i=0;
     do{
          readFrom(Buffer[i], input);
          written[i] = FALSE;
          i = i + 1;
     } while ( !end of file(input) && i != m );

     // 런의 생성
     while( !end of file(input) ){
          // 새로운 런 하나를 생성
          // 동결 플래그 초기화
          for( i=1; i<m; i++ )
               if( !written[i] )
                    frozen[i] = FALSE;
          while( any unfrozen records remain ){
               // 레코드 하나를 런에 출력
               Buffer[s] = smallest unfrozen record;
               lastKey = Buffer[s].key;
               written[s] = TRUE;
               frozen[s] = TRUE;
               if( !end of file(input) ){
                    readFrom(new Buffer[s], input);
                    written[s] = FALSE;
                    if( Buffer[s].key > lastKey )
                         frozen[s] = FALSE;
               }
          }
     }
     // 버퍼에 있는 나머지 레코드들을 출력
     appendToRun(unwritten Buffer[] records, ascending key order);
end replacementSelection()

이 대체 선택 방법이 입력 파일의 일부 정렬된 레코드들의 순서를 이용한다는 것은 분명하다. 입력 파일에 정렬된 레코드가 많으면 많을수록 한 개의 Run에 입력되는 레코드의 개수는 증가하게 된다.
이 방법을 이용했을 때 Run의 평균 예상 길이는 2m 레코드가 된다고 알려져 있다.

1. 다수의 레코드를 가지고 있는 파일을 n개의 서브파일로 나누어 이들에 각각 내부 정렬 기법을 적용한 것. [본문으로]