repetitionmust be changed to > after these modificationswe may now proceed to describe the entire algorithm in terms of procedure operating on the global array with elements procedure straightmerge(adens _mergesorts *var ijkltinteger(*index range of is * - *hmpqrintegerupbooleanbegin up :truep : repeat : :nif up then : : - :nl : * - else : : - :nj : * - endrepeat (*merge run from iand -sources to -destination*if > then : else : endm : -qif > then : else : endm : -rwhile ( ( do if [ia[jthen [ : [ ] : +hi : + : - else [ : [ ] : +hj : - : - end endwhile do [ : [ ] : +hj : - : - endwhile do [ : [ ] : +hi : + : - endh :-ht :kk :ll : until up :~upp : * until >nif ~up then for : to - do [ : [ +nend end end straightmerge analysis of mergesort since each pass doubles pand since the sort is terminated as soon as nit involves log(npasses each passby definitioncopies the entire set of items exactly once as consequencethe total number of moves is exactly log(nthe number of key comparisons is even less than since no comparisons are involved in the tail copying operations howeversince the mergesort technique is usually applied in connection with the use of peripheral storage devicesthe computational effort involved in the move operations dominates the effort of comparisons often by several orders of magnitude the detailed analysis of the number of comparisons is therefore of little practical interest