You want to select the best sort- ing algorithm to use on your classes example computer. The relevant parts of the computers architecture are the cache and the main memory. In particular, the machines memory can be viewed as a large array partitioned into a number of cache lines, each containing s consecutive locations of the memory array. In other words the first cache line consists of the first s memory locations, the second cache line consists of the next s memory locations etc. The cache mem- ory is a small fast memory that at any point in time contains a constant ((1)) number of these cache lines. The cache lines that are not in the cache are maintained in main memory. When- ever a user program accesses a memory location in a cache line that is in the cache, the access occurs with no main memory activity. Such a memory access is considered to be fast. If the memory location is not in the cache, however, the cache line on which it resides replaces some other cache line currently in the cache. In other words, the cache line that is being replaced is copied out to main memory and the desired cache line is copied into the cache. This event is called a cache miss. Since a cache miss involves a reference to main memory, this type of memory access is considered to be slow.

You decide to select your sorting algorithm based on the running time analysis given of the various sorting algorithms discussed before. However, after a while you realize that the analysis given in class does not account for the fact that the main memory operations required by a cache miss can take orders of magnitude longer than memory operations that only involve the cache. In order to account for the cost of the different memory operations you decide to analyze the sorting algorithms based on the number of cache misses they may require.

First you extend O-notation to two-variable functions (so as to free yourself from having to give exact answers when counting main memory operations).

Specifically:

O(f(x,y)) = {g(x,y) : there exist positive constants x0, y0, and c such that |g(x,y)| cf(x,y) for all x x0 and y y0}.

In answering the following questions, assume that the cache holds (1) cache lines and that the n numbers to be sorted are stored in an array of contiguous memory locations. Your answers should generally be worst-case analyses expressed in terms of n, the number of values to be sorted, and s, the number of values that fit in a cache line. Justify your answers by showing your analyses.

(a) Show that INSERTIONSORT has O(n^2/s) cache misses. Assuming that your code knows s, suggest a modification to INSERTIONSORT that achieves O(n^2/s^2) cache misses.

(b) Showthatthenumberofcachemissesgeneratedinmergingtwosortedarraysofm numbers apiece is O(m/s). How many cache misses are required by MERGESORT when accessing the input array?

(c) How many cache misses are generated when HEAPIFY is called on a node of height h? What is the total cost (in terms of cache misses) of BUILDHEAP? How many cache misses does HEAPSORT generate? (Use the array implementation for heaps given in the book.)

(d) How many cache misses does the PARTITION procedure in the book require for access to the input array? Make an intelligent guess as to the average number of cache misses that QUICKSORT requires. You need only provide an intuitive justification for your guess.

(e) Which sorting algorithm would you recommend to your boss and why?