where does this division process stopif we keep dividing by and count how many times we do thiswe get the series which is about seven levels of recursion this looks about right on the workshop appletsif you pick some point on the graph and count all the dotted lines directly above and below itthere will be an average of approximately seven (in figure because not all levels of recursion are shownonly four lines intersect any vertical slice of the graph table shows total of cells this is only an approximation because of roundoff errorsbut it' close to times the logarithm to the base of which is thusthis informal analysis suggests the validity of the *log running time for quicksort more specificallyin the section on partitioningwe found that there should be + comparisons and fewer than / swaps multiplying these quantities by log for various values of gives the results shown in table table swaps and comparisons in quicksort log *log comparisons( + )*log swapsfewer than / *log the log quantity used in table is actually true only in the best-case scenariowhere each subarray is partitioned exactly in half for random data the figure is slightly greater neverthelessthe quicksort and quicksort workshop applets approximate these results for and barsas you can see by running them and observing the swaps and comparisons fields because they have different cutoff points and handle the resulting small partitions differentlyquicksort performs fewer swaps but more comparisons than quicksort the number of swaps shown in table is the maximum (which assumes the data is inversely sortedfor random data the actual number of swaps turns out to be onehalf to two-thirds of the figures shown radix sort we'll close this by briefly mentioning sort that uses different approach the sorts we've looked at so far treat the key as simple numerical value that is compared with other values to sort the data the radix sort disassembles the key into digits and arranges the data items according to the value of the digits amazinglyno comparisons are necessary