External Sort

Two way Merge Sort

• Number of passes: $(1+\lceil lo{g}_{2}N\rceil )$
• IO: $2N\ast (1+\lceil lo{g}_{2}N\rceil )$
  Sort in input buffer, write it to output buffer. When output buffer is full, write it to disk.

K way Merge Sort

• $B$ is the total number of buffer pages available
• Sort Phase: Read $B$ pages at a time and write $\lceil \frac{N}{B}\rceil$ sorted runs back to disk
• Merge Phase: Combine up to $B-1$ runs in each pass
• Passes: $1+\lceil {\log }_{B-1}\lceil \frac{N}{B}\rceil \rceil$

Optimization

Double Buffering

Prefetch the next run in the background and storing it in a second buffer while the system is processing the current run. To overlap disk IO and CPU time This optimization requires the use of multiple threads, since the prefetching should occur while the computation for the current run is happening.

Comparison Optimizations

Links

• 15445.courses.cs.cmu.edu/fall2023/notes/10-sorting.pdf