the algorithmic problem using as few block transfers as possible the most classic domain for such external-memory algorithms is the sorting problem multi-way merge-sort an efficient way to sort set of objects in external memory amounts to simple external-memory variation on the familiar merge-sort algorithm the main idea behind this variation is to merge many recursively sorted lists at timethereby reducing the number of levels of recursion specificallya high-level description of this multi-way merge-sort method is to divide into subsets of roughly equal sizerecursively sort each subset and then simultaneously merge all sorted lists into sorted representation of if we can perform the merge process using only ( /bdisk transfersthenfor large enough values of nthe total number of transfers performed by this algorithm satisfies the following recurrencet(nd ( /dcn/bfor some constant > we can stop the recursion when <bsince we can perform single block transfer at this pointgetting all of the objects into internal memoryand then sort the set with an efficient internal-memory algorithm thusthe stopping criterion for (nis ( if / <= this implies closed-form solution that (nis (( / )logd( / ))which is (( / )log( / )/logdthusif we can choose to be ( / )then the worst-case number of block transfers performed by this multi-way merge-sort algorithm will be quite low we choose ( / ) / the only aspect of this algorithm left to specifythenis how to perform the -way merge using only ( /bblock transfers multi-way merging we perform the -way merge by running "tournament we let tbe complete binary tree with external nodesand we keep entirely in internal memory we associate each external node of with different sorted list we initialize by reading into each external node ithe first object in this has the effect of reading into internal memory the first block of each sorted list for each internal-node