subarray bounds (left and righton stackand using loop instead of recursion to oversee the partitioning of smaller and smaller subarrays the idea in doing this is to speed up the program by removing method calls howeverthis idea arose with older compilers and computer architectureswhich imposed large time penalty for each method call it' not clear that removing recursion is much of an improvement for modern systemswhich handle method calls more efficiently efficiency of quicksort we've said that quicksort operates in ( *logntime as we saw in the discussion of mergesort in this is generally true of the divide-and-conquer algorithmsin which recursive method divides range of items into two groups and then calls itself to handle each group in this situation the logarithm actually has base of the running time is proportional to *log you can get an idea of the validity of this *log running time for quicksort by running one of the quicksort workshop applets with random bars and examining the resulting dotted horizontal lines each dotted line represents an array or subarray being partitionedthe pointers leftscan and rightscan moving toward each othercomparing each data item and swapping when appropriate we saw in the "partitioningsection that single partition runs in (ntime this tells us that the total length of all the dotted lines is proportional to the running time of quicksort but how long are all the linesmeasuring them with ruler on the screen would be tediousbut we can visualize them different way there is always line that runs the entire width of the graphspanning bars this results from the first partition there will also be lines (one below and one above the first linethat have an average length of / barstogether they are again bars long then there will be lines with an average length of / that again total barsthen lines linesand so on figure shows how this looks for and lines in this figure solid horizontal lines represent the dotted horizontal lines in the quicksort appletsand captions like / cells long indicate averagenot actualline lengths the circled numbers on the left show the order in which the lines are created each series of lines (the eight / linesfor examplecorresponds to level of recursion the initial call to recquicksort(is the first level and makes the first linethe two calls from within the first call--the second level of recursion--make the next two linesand so on if we assume we start with cellsthe results are shown in table