External Sorting
Analysis
Review
- N: Number of pages being sorted.
- B: Number of pages that fit in memory, for sorting.
| Pass# |
Run length |
Number of runs |
| 1 |
B |
N / B |
| 2 |
B(B-1) |
N / B(B-1) |
| 3 |
B(B-1)2 |
N / B(B-1)2 |
| ... |
... |
... |
| i |
B(B-1)i-1 |
N / B(B-1)i-1 |
| ... |
... |
... |
| k |
B(B-1)k-1 = N |
N / B(B-1)k-1 = 1 |
|