sorting posby making use of the variable startingindexwhich is maintained at lines and except for thatlines to in figure are the same as lines to in figure the running time of this version of radix sort is linear in the total number of characters in all the strings (each character appears exactly once at line and the statement at line executes precisely as many times as the line radix sort for strings will perform especially well when the characters in the string are drawn from reasonably small alphabet and when the strings either are relatively short or are very similar because the ( log ncomparison-based sorting algorithms will generally look only at small number of characters in each string comparisononce the average string length starts getting largeradix sort' advantage is minimized or evaporates completely external sorting so farall the algorithms we have examined require that the input fit into main memory there arehoweverapplications where the input is much too large to fit into memory this section will discuss external sorting algorithmswhich are designed to handle very large inputs why we need new algorithms most of the internal sorting algorithms take advantage of the fact that memory is directly addressable shellsort compares elements [iand [ -hk in one time unit heapsort compares elements [iand [ * + in one time unit quicksortwith median-of-three partitioningrequires comparing [left] [center]and [rightin constant number of time units if the input is on tapethen all these operations lose their efficiencysince elements on tape can only be accessed sequentially even if the data are on diskthere is still practical loss of efficiency because of the delay required to spin the disk and move the disk head to see how slow external accesses really arecreate random file that is largebut not too big to fit in main memory read the file in and sort it using an efficient algorithm the time it takes to read the input is certain to be significant compared to the time to sort the inputeven though sorting is an ( log noperation and reading the input is only (nmodel for external sorting the wide variety of mass storage devices makes external sorting much more device dependent than internal sorting the algorithms that we will consider work on tapeswhich are probably the most restrictive storage medium since access to an element on tape is done by winding the tape to the correct locationtapes can be efficiently accessed only in sequential order (in either directionwe will assume that we have at least three tape drives to perform the sorting we need two drives to do an efficient sortthe third drive simplifies matters if only one tape drive is presentthen we are in troubleany algorithm will require ( tape accesses