External Sorting¶
引入¶
Why can’t we simply do quicksort on a disk?
To get a[i] on：
- internal memory – \(O(1)\)
- hard disk
- find the track;
- find the sector;
- find a[i] and transmit.
原始做法¶
Given 10,000,000 records of 128 bytes each, and the size of the internal memory is 4MB. How many passes we have to do?
Answer: 1 + log(320 runs) = 1 + 9
进阶¶
k-way merge¶
这种做法旨在减少pass式子中的底数。
但是这要求\(2k\)条磁带。