the simple algorithm the basic external sorting algorithm uses the merging algorithm from mergesort suppose we have four tapesta ta tb tb which are two input and two output tapes depending on the point in the algorithmthe and tapes are either input tapes or output tapes suppose the data are initially on ta suppose further that the internal memory can hold (and sortm records at time natural first step is to read records at time from the input tapesort the records internallyand then write the sorted records alternately to tb and tb we will call each set of sorted records run when this is donewe rewind all the tapes suppose we have the same input as our example for shellsort ta ta tb tb if then after the runs are constructedthe tapes will contain the data indicated in the following figure ta ta tb tb now tb and tb contain group of runs we take the first run from each tape and merge themwriting the resultwhich is run twice as longonto ta recall that merging two sorted lists is simplewe need almost no memorysince the merge is performed as tb and tb advance then we take the next run from each tapemerge theseand write the result to ta we continue this processalternating between ta and ta until either tb or tb is empty at this point either both are empty or there is one run left in the latter casewe copy this run to the appropriate tape we rewind all four tapes and repeat the same stepsthis time using the tapes as input and the tapes as output this will give runs of we continue the process until we get one run of length this algorithm will require log( / )passesplus the initial run-constructing pass for instanceif we have million records of bytes eachand four megabytes of internal memorythen the first pass will create runs we would then need nine more passes to complete the sort our example requires log / more passeswhich are shown in the following figuresta ta tb tb