sec external sorting falling snow future snow existing snow snowplow movement start time figure the snowplow analogy showing the action during one revolution of the snowplow circular track is laid out straight for purposes of illustrationand is shown in cross section at any time the most snow is directly in front of the snowplow as the plow moves around the trackthe same amount of snow is always in front of the plow as the plow moves forwardless of this is snow that was in the track at time more is snow that has fallen since this is the place least recently plowed at any instantthere is certain amount of snow on the track snow is constantly falling throughout the track at steady ratewith some snow falling "in frontof the plow and some "behindthe plow (on circular trackeverything is actually "in frontof the plowbut figure illustrates the idea during the next revolution of the plowall snow on the track is removedplus half of what falls because everything is assumed to be in steady stateafter one revolution snow is still on the trackso snow must fall during revolutionand snow is removed during revolution (leaving snow behindat the beginning of replacement selectionnearly all values coming from the input file are greater ( "in front of the plow"than the latest key value output for this runbecause the run' initial key values should be small as the run progressesthe latest key value output becomes greater and so new key values coming from the input file are more likely to be too small ( "after the plow")such records go to the bottom of the array the total length of the run is expected to be twice the size of the array of coursethis assumes that incoming key values are evenly distributed within the key range (in terms of the snowplow analogywe assume that snow falls evenly throughout the tracksorted and reverse sorted inputs do not meet this expectation and so change the length of the run multiway merging the second stage of typical external sorting algorithm merges the runs created by the first stage assume that we have runs to merge if simple two-way merge is usedthen runs (regardless of their sizeswill require log passes through the file while should be much less than the total number of records (because