external-memory sorting in addition to data structuressuch as mapsthat need to be implemented in external memorythere are many algorithms that must also operate on input sets that are too large to fit entirely into internal memory in this casethe objective is to solve the algorithmic problem using as few block transfers as possible the most classic domain for such external-memory algorithms is the sorting problem multiway 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 multiway merge-sort method is to divide into subsets sd of roughly equal sizerecursively sort each subset si 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 (( /blogd ( / ))which is (( /blog( / )log dthusif we can choose to be th( / )where is the size of the internal memorythen the worst-case number of block transfers performed by this multiway mergesort algorithm will be quite low for reasons given in the next sectionwe choose ( / the only aspect of this algorithm left to specifythenis how to perform the -way merge using only ( /bblock transfers