I&C SCI 46 Lecture Notes - Lecture 30: Merge Sort, Sorting Algorithm
25 Oct 2016
School
Department
Course
Professor
Document Summary
In this lecture we will continue our examination of algorithms that use more space than is available in main memory. We will analyze them with respect to how often they move blocks of data between main and external memory (discussed in the previous lecture). Typically the cost of such memory transfers dominates the cost of executing code on the block while it is in memory. That is, a transfer between main and external memory might take 10 milliseconds, while processing the data in the block might take microseconds (a few 1/1000ths of a millisecond). A processor executing 10^9 instructions per second can process 10^7 (10 million) instructions in 10 ms. So, we can virtually ignore the time taken to process each block retrieved from memory. Our external sorting algorithm is a variant of merge sort, which can be run efficiently in terms of external storage use.
