Consider the natural join of the relation R(A,B) and S(A,C) on attribute A. Neither relations have any indexes built on them. Assume that R and S have 80,000 and 20,000 blocks, respectively. The cost of a join is the number of its block I/Os accesses. If the algorithms need to sort the relations, they must use two-pass multi-way merge sort.

Assume that there are 110,000 blocks available in the main memory. We like to have the output sorted based on the join attribute. What is the fastest join algorithm to compute the join of R and S? What is the cost of this algorithm?