table incorrect result of mergesort program the example of this programming mistake is typical for many programming situations the mistake is caused by an oversight of one of the possible consequences of presumably simple operation it is also typical in the sense that serval ways of correcting the mistake are open and that one of them has to be chosen often there exist two possibilities that differ in very importantfundamental way we recognize that the operation of distribution is incorrectly programmed and does not satisfy the requirement that the number of runs differ by at most we stick to the original scheme of operation and correct the faulty procedure accordingly we recognize that the correction of the faulty part involves far-reaching modificationsand we try to find ways in which other parts of the algorithm may be changed to accommodate the currently incorrect part in generalthe first path seems to be the safercleaner onethe more honest wayproviding fair degree of immunity from later consequences of overlookedintricate side effects it isthereforethe way toward solution that is generally recommended it is to be pointed outhoweverthat the second possibility should sometimes not be entirely ignored it is for this reason that we further elaborate on this example and illustrate fix by modification of the merge procedure rather than the distribution procedurewhich is primarily at fault this implies that we leave the distribution scheme untouched and renounce the condition that runs be equally distributed this may result in less than optimal performance howeverthe worst-case performance remains unchangedand moreoverthe case of highly unequal distribution is statistically very unlikely efficiency considerations are therefore no serious argument against this solution if the condition of equal distribution of runs no longer existsthen the merge procedure has to be changed so thatafter reaching the end of one filethe entire tail of the remaining file is copied instead of at most one run this change is straightforward and is very simple in comparison with any change in the distribution scheme (the reader is urged to convince himself of the truth of this claimthe revised version of the merge algorithm is shown below in the form of function procedureprocedure copyrun (var xyruns rider)begin (*from to *repeat runs copy(xyuntil eor end copyrunprocedure naturalmerge (srcfiles file)files filevar linteger(*no of runs merged* files filer runs riderbegin runs set( src)repeat :files new("test ")files set( ) :files new("test ")files set ( )(*distribute from to and *repeat copyrun( )(adens _mergesorts *