Binary Sort/Merge 질문

배경지식

우선 외부 정렬을 이해하기 위해서는 2가지 배경지식이 필요합니다. 첫번째는 Merge Sort의 알고리즘이고, 두 번째는 컴퓨터가 파일을 읽는 방법입니다. 컴퓨터공학과이시니 둘의 배경 지식은 알고 있다고 가정하고 설명드리겠습니다.

작동 방식

Binary Sort/Merge의 작동 순서는 다음과 같습니다.

1. 메모리 내에서 정렬할 수 있는 크기(Run)만큼은 일단 내부 정렬하고 파일(File X)에 이어서 붙인다.
   • 내부 정렬 알고리즘은 상관 없음
   • Quick Sort, Merge Sort, Heap Sort 등등 모두 가능
2. 정렬된 그룹이 유지되도록 두 파일(File 1, File 2)로 나눈다.
3. 정렬된 그룹에서 한 원소씩 뽑아 Merge Sort 한다.
   • 한 원소씩 뽑기 위해서 두 파일로 나눈 것입니다.
   • 컴퓨터가 파일을 읽는 특징 때문에 한 파일에서 멀리 떨어진 두 원소를 뽑기 힘듭니다.
4. Merge Sort된 결과를 한 파일(File X)에 이어서 저장한다.
5. 정렬이 완료될때 까지 2~4를 반복한다.

보내주신 그림 설명

• 그림에서 소괄호는 정렬된 그룹을 나타냅니다.
• 그림에서는 Sorting Phase(내부정렬)가 완료된 후 두개의 파일로 나눠져 있습니다.
  • 앞서 설명드렸다시피 내부 정렬된 그룹을 한 파일에 모드 저장한 후 정렬된 그룹이 유지되도록 두 파일로 나눠도 상관 없습니다.
  • Sorting Phase의 결과를 두 개의 파일에 나눠 담을 수 있다면 그룹이 유지되도록 나누는 과정을 생략할 수 있습니다.
    • 디스크 입출력에는 시간이 많이 소모됩니다.
    • 한 단계를 생략하면 많은 시간 소모를 줄일 수 있습니다.
• 추가 설명
  • 그림의 Binary Sort/Merge에서 디스크 입출력을 줄이기 위해 첫 번째 내부 정렬 결과를 두 파일에 나누었듯이 Merge Sort의 결과를 두 파일에 나누면 디스크 입출력을 줄일 수 있습니다.
    • 이를 이용한 것이 Balanced Binary Sort/Merge 입니다.