External Sorting
Analysis
- Traditional complexity analysis counts comparisons, or other
CPU operations (e.g. data copies).
- For database operations, the most important measure is the number
of pages read or written.
- For external sorting, the best possible performance requires
every page to be read once, and every (sorted) page to be
written once.
- This is one pass.
- Each pass reads and writes the entire file.
|