<Algorithm> External Sort ① MergeSort

본 게시물은 영남대학교 조행래 교수님의 강의를 기반으로 작성되었습니다.

1. Binary Merge Sort

• 주 기억장치의 크기를 넘어서는 파일을 다룰 때 보조기억장치의 도움을 받아 데이터를 정렬하는 알고리즘이다.-> 외부정렬의 개념
• 쉽게 보면 DRAM의 크기보다 큰 데이터를 가진 파일을 정렬해야하는 상황에서 SSD나 HDD의 도움을 받아서 정렬을 한다고 이해하면 쉽다.
• 외부 정렬시 Run이라는 개념이 도입되는데, 이는 정렬할 파일을 몇개의 그룹으로 나눌때 나눠진 그룹을 일컫는 하나의 단위라고 보면된다. 즉, 주기억장치에 적재가 가능한 사이즈여야 한다.
• Run의 크기의 경우 통상적으로는 momory의 크기보다 작다.
• 기본적으로 merge-sort 방식을 따라서 정렬한다.
• 각 run에 대해 내부정렬 후 다른 파일에 저장한다.
• 병합된 run의 수가 1이 될때까지 병합을 반복한다.(가장 큰 덩어리가 될 때까지)
• Run의 개수와 Run의 크기는 서로 다른 값이 될수 있다.

2. Binary Merge Sort

• Sorting Phase와 Merging Phase로 나뉜다.
• 초기 run들을 정렬 한 뒤, 2개의 외부 파일에 저장하는 방식
• 초기 run의 수가 R이면,Level의 수 = [log₂R] + 1
• 전체 병합 단계의 수 : [log₂R]
• 여러번의 재분배가 필요해서 성능이 좋진 않다
• Input File(Run=3, 메모리의 크기가 데이터 3개까지 저장가능)
  • (50,110,95) (10,100,36) (153,40,120) (60,70,130) (22,140,80)
• Sorting Phase 완료후
  • File1 : (50,95,110) (40 120 153) (22 80 140)
  • File2 : (10 36 100) (60 70 130)
• 첫 번째 병합 결과:
  • File3 : (10 36 50 95 100 110) (40 60 70 120 130 153) (22 80 140)
• 재분배 결과 :
  • File1 : (10 35 50 95 100 110) (22 80 140)
  • Fiel2 : (40 60 70 120 130 153)
  • File3 : 비어있음
• 두번째 병합 결과:
  • File3 : (10 35 40 50 60 70 95 100 110 120 130 153) (22 80 140)
• 다시 재분배... :
  • File1 : (10 35 40 50 60 70 95 100 110 120 130 153)
  • File2 : (22 80 140)
  • File3 : 비어있음
• 세번째 병합!! :
  • File3 : (10 22 35 40 50 60 70 80 95 100 110 120 130 140 153)

3. Balanced Binary Merge Sort

• Output file의 수 = Input file의 수(바이너리니까 각각 2개!)
• Iuput file : (50,110,95) (10,100,36) (153,40,120) (60,70,130) (22,140,80)
• Sorting Phase의 완료 후 :
  • File1 : (50,95,110) (40 120 153) (22 80 140)
  • File2 : (10 36 100) (60 70 130)
• 첫 번째 병합 결과
  • File3 : (10 36 50 95 100 110), (22 80 140)
  • File4 : (40 60 70 120 130 153)
• 두 번째 병합 결과
  • File1 : (10 36 40 50 60 70 95 100 110 120 130 153)
  • File2 : (22 80 140)
• 세 번째 병합 결과
  • File3 : (10 22 35 40 50 60 70 80 95 100 110 120 130 140 153)

4. Balanced k-way Merge Sort(k > 2)

• k개의 수만큼 input과 output 파일의 수를 설정!
  • Run의 개수가 N인 경우,[log_kN]만큼의 병합단계의 수를 가진다!
  • K의 값은 아무리 커도 메모리의 크기보다 클 수는없다.
  • Input file : (50,110,95) (10,100,36) (153,40,120) (60,70,130) (22,140,80)
  • Soting Phase 완료후 :
    • File 1 : (50 95 110) (60 70 130)
    • File 2 : (10 36 100) (22 80 140)
    • File 3 : (40 120 153)
  • 첫번째 병합의 결과 :
    • File 4 : (10 36 40 50 95 100 110 120 153)
    • File 5 : (22 60 70 80 130 140)
    • File 6 : 비어있음
  • 두번째 병합의 결과 :
    • File 1 : (10 22 35 40 50 60 70 80 95 100 110 120 130 140 153)

5. Polyphase Merge Sort

• 빈 파일을 output으로 사용하여 공간을 효율성 증가!
• Iuput file : (50,110,95) (10,100,36) (153,40,120) (60,70,130) (22,140,80)
• Sorintg Phase 완료 후 :
  * File1 : (50,95,110) (40 120 153) (22 80 140)
  * File2 : (10 36 100) (60 70 130)
• 첫번째 병합의 결과 :
  * File1 : (22 80 140)
  * File2 : 비었음
  * File3 : (10 36 50 95 100 110) (40 60 70 120 130 153)
• 두번째 병합 결과 :
  * File1 : 비었음
  * File2 : (10 22 36 50 80 95 100 110 140)
  * File3 : (40 60 70 120 130 153)
• 세번째 병합 결과 :
  * File1 : (10 22 40 36 50 60 70 80 95 100 110 120 130 140 153)