smaller than the cutoff when quicksort is finishedthe array will be almost sorted you then apply the insertion sort to the entire array the insertion sort is supposed to operate efficiently on almost-sorted arraysand this approach is recommended by some expertsbut on our installation it runs very slowly the insertion sort appears to be happier doing lot of small sorts than one big one removing recursion another embellishment recommended by many writers is removing recursion from the quicksort algorithm this involves rewriting the algorithm to store deferred 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 items and swapping when appropriate we saw in the section on partitioning that single partition runs in (ntime this tells us that the total length of all the lines is proportional to the running time of quicksort but how long are all the linesit would be tedious to measure them with ruler on the screenbut we can visualize them different way there is always one line that runs the entire width of the graphspanning bars this results from the first partition there will also be two lines (one below and one above the first linethat have an average length of / barstogether they are again bars long then there will be four lines with an average length of / that again total barsthen lines and so on figure shows how this looks for and lines