no one so far has been able to analyze the shellsort' efficiency theoreticallyexcept in special cases based on experimentsthere are various estimateswhich range from / / ( down to ( table shows some of these estimated (valuescompared with the slower insertion sort and the faster quicksort the theoretical times corresponding to various values of are shown note that ex/ means the yth root of raised to the power thus if is / is the square root of which is , also(lognmeans the log of nsquared this is often written log nbut that' easy to confuse with log nthe logarithm to the base of table estimates of shellsort running time (value type of sort items items , items , items insertionetc , , , , , / shellsort , , , , shellsort , , *(logn / shellsort , , / shellsort , , *logn quicksortetc , , for most data the higher estimatessuch as / are probably more realistic partitioning partitioning is the underlying mechanism of quicksortwhich we'll explore nextbut it' also useful operation on its ownso we'll cover it here in its own section to partition data is to divide it into two groupsso that all the items with key value higher than specified amount are in one groupand all the items with lower key value are in another it' easy to imagine situations in which you would want to partition data maybe you want to divide your personnel records into two groupsemployees who live within miles of the office and those who live farther away or school administrator might want to divide students into those with grade point averages higher and lower than so as to know who deserves to be on the dean' list the partition workshop applet