and we associate the smaller of the two with we repeat this comparison test at the next level up in tand the nextand so on when we reach the root of twe will associate the smallest object from among all the lists with this completes the initialization for the -way merge (see figure figure -way merge we show five-way merge with in general step of the -way mergewe move the object associated with the root of into an array we are building for the merged list we then trace down tfollowing the path to the external node that came from we then read into the next object in the list if was not the last element in its blockthen this next object is already in internal memory otherwisewe read in the next block of to access this new object (if is now emptyassociate the node with pseudo-object with key +we then repeat the minimum computations for each of the internal nodes from to the root of this again gives us the complete tree we then repeat this process of moving the object from the root of to the merged list 'and rebuilding tuntil is empty of objects each step in the merge takes (log dtimehencethe internal time for the -way merge is (nlogdthe number of transfers performed in merge is ( / )since we scan each list in order onceand we write out the merged list once thuswe haveproposition given an array-based sequence of elements stored in external memorywe can sort using (( / )log( / )/log( / )transfers and ( log ninternal cpu timewhere is the size of the internal memory and is the size of block exercises for source code and help with exercisesplease visit java datastructures net