¡EGeneral Sort-Merge method:
¡@ ¡EBreak file into sorted blocks (runs)
¡@¡@ + Merge into larger block
¡EGoal:
¡@ Reduce # passes
¡EMemory Hierarchy
¡EBalance P-way Merge
¡@ <1> Generate Initial Runs:
¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@A S O R T I N G E X A M P L E
¡@¡@¡@ tape1¡@ A O S ¡E D M N ¡E A E X ¡ø¡@¡@ ¡õ
¡@¡@¡@ tape2¡@ I R T ¡E E G R ¡E L M P ¡ö¡@ A O S
¡@¡@¡@ tape3¡@ A G N ¡E G I N ¡E E¡@¡@ ¡ú¡@ Internal Memory
¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@ M = 3, P = 3
¡@ <2>P-way Merge
¡@¡@¡@ tape4¡@ A A G I N O R S T ¡E
¡@¡@¡@ tape5¡@ D E G I M N N R ¡E
¡@¡@¡@ tape6¡@ A E E L M P X ¡E
¡@¡@¡@ tape1¡@ A A A D E E E G ....
¡@ ¡ELog p (N/M)¡@ passes
¡@ ¡E4-tapes are enough
¡EReplacement Selection
¡@¡@ Priority Quene
¡@ ¡EFor P-way Merge
¡@¡@¡@ tape1:¡@ A O S ¡E D M N ¡E ....
¡@¡@¡@ tape2:¡@ I R T ¡E E G R ¡E ....
¡@¡@¡@ tape3:¡@ A G N ¡E G I N ¡E ....
¡@¡@¡@ tape4:¡@ A A G I N O R S T ¡E
¡@¡@¡@¡@ Heap, size P:¡@
¡@¡@¡@¡@ 1¡@¡@ 2¡@¡@ 3
¡@¡@¡@¡@ A¡@¡@ I¡@¡@ A
¡@¡@¡@¡@ A¡@¡@ I¡@¡@ O
¡@¡@¡@¡@ G¡@¡@ I¡@¡@ O
¡@¡@¡@¡@ I¡@¡@ N¡@¡@ O
¡@¡@¡@¡@ N¡@¡@ R¡@¡@ O
¡@¡@¡@¡@ O¡@¡@ O¡@¡@ ¡E¡÷¡Û
¡@¡@¡@¡@ R¡@¡@ S¡@¡@ ¡E
¡@¡@¡@¡@ S¡@¡@ T¡@¡@ ¡E
¡@¡@¡@¡@ T¡@¡@ ¡E¡@¡@ ¡E
¡@ ¡EForm Initial Run
¡@
¡@¡@¡@ tape1: A O R S T¡E A D E G I M N R X ¡E E ¡E
¡@¡@¡@ tape2: G I N N ¡E A E G L M P ¡E
¡@ ¡ERandom Keys ¡÷ Run Size ¡Ü 2M
¡@¡@¡@¡@¡@ Some order¡@ ¡÷ Longer runs
¡@¡@¡@¡@¡@ (Example:¡@
key, less than M
¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@ larger key before it ¡÷ 1 run)
¡@ ¡EM, Ptapes ¡÷ log p(N / 2M)¡@ passes
Pratical Considerations
¡@ ¡EOverlap Input, Output, & Computing
¡@ ¡EDouble Buffering : P-way merging
¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@ (2P : Input Buffer,
¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@¡@ P : Output Buffer)
¡@¡@¡@ tape1: 1, 3, 5, 7, 8, 9, ....
¡@¡@¡@ tape2: 2, 4, 6, 15, 20, 25, ....
¡@¡@¡@ tape3: 1, 2, 3, 4, ....
¡@¡@¡@¡@¡@¡@
¡@ ¡EForcasting [P+1 input Buffers],[2 output Buffers]
¡@¡@¡@ Example: 3 < 4, ¡ï¡@
¡ESystem Architecture
¡@¡@¡@¡@
¡@ ¡EPratical Consideration
¡@¡@¡@ ¡EOverlapping : Input, Output, Computing
¡@¡@¡@ ¡Edouble buffering
¡@¡@¡@ ¡EForecasting
¡EPolyphase merging
¡@ ¡ENo need to (1) use 2P tapes
¡@¡@¡@¡@¡@¡@ or (2) copy files between merging phases
¡@¡@¡@ Example:
¡@¡@¡@ tape1: A O R S T ¡E I N ¡E A G N ¡E D E M R ¡E G I N ¡E
¡@¡@¡@ tape2: E G X ¡E A M P ¡E E L ¡E
¡@¡@¡@ tape3:
¡@¡@¡@ tape1: D E M R ¡E G I N ¡E
¡@¡@¡@ tape2:
¡@¡@¡@ tape3: A E G O R S T X ¡E A I M N P ¡E A E G L N ¡E
¡@¡@¡@ tape1:
¡@¡@¡@ tape2: A D E E G M O R R S T X ¡E A G I I M N N P ¡E
¡@¡@¡@ tape3: A E G L N ¡E
¡@¡@¡@ tape1: A A D E ............¡E (sorted file)
¡@¡@¡@ tape2:
¡@¡@¡@ tape3:
¡@¡@¡@ How to distribute initial runs ?
¡@¡@¡@ T1¡@¡@ T2¡@¡@ T3¡@¡@¡@ T4
¡@¡@¡@ 0¡@¡@¡@ 13¡@¡@ 11¡@¡@¡@ 7¡@ 13 = 7 + 4 + 2
¡@¡@¡@ 7¡@¡@¡@ 6¡@¡@¡@ 4¡@¡@¡@ 0¡@ Generalized Fibonanci #s.
¡@¡@¡@ 3¡@¡@¡@ 2¡@¡@¡@ 0¡@¡@¡@ 4
¡@¡@¡@ 1¡@¡@¡@ 0¡@¡@¡@ 2¡@¡@¡@ 2
¡@¡@¡@ 1¡@¡@¡@ 0¡@¡@¡@ 0¡@¡@¡@ 0
¡EVitual Memory Environment (Easy!)
¡@ ¡EPage demanding + Least Recently Used (LRU) page
¡@ ¡ELocality of Reference
¡@ ¡EInitial Sorting with few locality works well
¡@¡@¡@ Example: Quick sort: 2 localities
¡@¡@¡@¡@¡@¡@¡@¡@ Radix sort: 0 locality
¡@¡@¡@¡@¡@¡@¡@¡@