number of passes: $1+ \lceil log_2 (N/M) \rceil$
seek time: O(number of passes)
a k-way merge
number of passes: $1+ \lceil log_k (N/M) \rceil$
require 2k tapes
polyphase merge
require k+1 tapes
Huffman tree
Total merge time = O ( the weighted external path length )
If the number of runs is a Fibonacci number $F_N$, then the best way to distribute them is to split them into $F_{N–1}$ and $F_{N–2}$ .
For a k-way merge, $F_N^{(k)} = F_{N-1}^{(k)}+F_{N-2}^{(k)}$, where $F_N^{(k)}=0 \; (0 \leq N \leq k-2), F_{k-1}^{(k)}=1$
Exercises
hardware
外部排序主要开销在I/O上
$\lceil 1+log_2(100,000,000 \times 256 \div 128 \div 10^6) \rceil = 9$
Huffman tree，每次挑最短的两条链合并
