partial merge the destination is switched from the lower to the upper end of the destination arrayor vice versato guarantee equal distribution onto both destinations if the destination of the merged items is the lower end of the destination arraythen the destination index is kand is incremented after each move of an item if they are to be moved to the upper end of the destination arraythe destination index is land it is decremented after each move in order to simplify the actual merge statementwe choose the destination to be designated by at all timesswitching the values of the variables and after each -tuple mergeand denote the increment to be used at all times by hwhere is either or - these design discussions lead to the following refinementh : : (* no of items to be merged*repeat :pr :pm : *pmerge items from -source with items from -source destination index is increment by hh :-hexchange and until in the further refinement step the actual merge statement is to be formulated here we have to keep in mind that the tail of the one subsequence which is left non-empty after the merge has to be appended to the output sequence by simple copying operations while ( ( do if [ia[jthen move an item from -source to -destinationadvance and kq : - else move an item from -source to -destinationadvance and kr : - end endcopy tail of -sequencecopy tail of -sequence after this further refinement of the tail copying operationsthe program is laid out in complete detail before writing it out in fullwe wish to eliminate the restriction that be power of which parts of the algorithm are affected by this relaxation of constraintswe easily convince ourselves that the best way to cope with the more general situation is to adhere to the old method as long as possible in this example this means that we continue merging -tuples until the remainders of the source sequences are of length less than the one and only part that is influenced are the statements that determine the values of and the following four statements replace the three statements :pr :pm : - * andas the reader should convince himselfthey represent an effective implementation of the strategy specified abovenote that denotes the total number of items in the two source sequences that remain to be mergedif > then : else : endm : -qif > then : else : endm : - in additionin order to guarantee termination of the programthe condition nwhich controls the outer