External-Memory Sorting (lecture notes)

When data do not fit in main memory (RAM), external (or secondary) memory is used. Magnetic disks are the most commonly used type of external memory. When compared to RAM, disks have these properties (see chapter 18 of [1] for a more thorough discussion): 1. Usually disks can store much more data than RAM. 2. Access to data on disk drives is much slower than access to RAM (by orders of mag-nitude). 3. Because of the mechanics of disk drives, it takes a lot of time to access a random byte on a disk, but it is relatively fast to transfer that byte and subsequent bytes from the disk to RAM. This means that it is beneficial to access data on the disk in large portions called blocks or pages. The block sizes from 2Kb to 16Kb are common for modern disk drives. Because access to disk drives is much slower than access to RAM, analysis of external-memory algorithms and data structures usually focuses on the number of disk accesses (I/O operations), not the CPU cost. When data is stored on the disk, algorithms that are efficient in main memory may not b