howeveris scanned in strictly sequential fashion later version of merge sort will then be based on the sequence structureallowing comparison of the two programs and demonstrating the strong dependence of the form of program on the underlying representation of its data single array may easily be used in place of two sequencesif it is regarded as double-ended instead of merging from two source fileswe may pick items off the two ends of the array thusthe general form of the combined merge-split phase can be illustrated as shown in fig the destination of the merged items is switched after each ordered pair in the first passafter each ordered quadruple in the second passetc thus evenly filling the two destination sequencesrepresented by the two ends of single array after each passthe two arrays interchange their rolesthe source becomes the new destinationand vice versa destination source merge distribute fig straight merge sort with two arrays further simplification of the program can be achieved by joining the two conceptually distinct arrays into single array of doubled size thusthe data will be represented by aarray * of item and we let the indices and denote the two source itemswhereas and designate the two destinations (see fig the initial data areof coursethe items an- clearlya boolean variable up is needed to denote the direction of the data flowup shall mean that in the current pass components an- will be moved up to the variables an - whereas ~up will indicate that an - will be transferred down into an- the value of up strictly alternates between consecutive passes andfinallya variable is introduced to denote the length of the subsequences to be merged its value is initially and it is doubled before each successive pass to simplify matters somewhatwe shall assume that is always power of thusthe first version of the straight merge program assumes the following formprocedure straightmergevar ijklpintegerupbooleanbegin up :truep : repeat initialize index variablesif up then : : - :nl : * - else : : - :nj : * - endmerge -tuples from iand -sources to kand -destinationsup :~upp : * until end straightmerge in the next development step we further refine the statements expressed in italics evidentlythe merge pass involving items is itself sequence of merges of sequencesi of -tuples between every such