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 the table is the maximum (which assumes the data is inversely sortedfor random data the actual number of swaps turns out to be half to two thirds of the figures shown summary the shellsort applies the insertion sort to widely spaced elementsthen less widely spaced elementsand so on the expression -sorting means sorting every nth element sequence of numberscalled the interval sequenceor gap sequenceis used to determine the sorting intervals in the shellsort widely used interval sequence is generated by the recursive expression = * + where the initial value of is if an array holds , itemsit could be -sorted -sorted -sorted -sorted -sortedand finally -sorted the shellsort is hard to analyzebut runs in approximately ( *(logn) time this is much faster than the ( algorithms like insertion sortbut slower than the ( *lognalgorithms like quicksort to partition an array is to divide it into two subarraysone of which holds items with key values less than specified valuewhile the other holds items with keys greater or equal to this value the pivot value is the value that determines into which group an item will go during partitioningitems smaller than the pivot value go in the left grouplarger items go in