end find if we assume that on the average each split halves the size of the partition in which the desired quantile liesthen the number of necessary comparisons is / / it is of order this explains the power of the program find for finding medians and similar quantilesand it explains its superiority over the straightforward method of sorting the entire set of candidates before selecting the -th (where the best is of order *log( )in the worst casehowevereach partitioning step reduces the size of the set of candidates only by resulting in required number of comparisons of order againthere is hardly any advantage in using this algorithmif the number of elements is smallsayfewer than comparison of array sorting methods to conclude this parade of sorting methodswe shall try to compare their effectiveness if denotes the number of items to be sortedc and shall again stand for the number of required key comparisons and item movesrespectively closed analytical formulas can be given for all three straight sorting methods they are tabulated in table the column headings minmaxavg specify the respective minimamaximaand values averaged over all npermutations of items min avg max straight insertion cn- ( )/ ( )/ ( - ( - )/ ( )/ straight selection ( )/ ( )/ ( )/ ( - *(ln( / ( - straight exchange ( - )/ ( - )/ ( - )/ ( - )* ( - )* table comparison of straight sorting methods no reasonably simple accurate formulas are available on the advanced methods the essential facts are that the computational effort needed is * in the case of shellsort and is * *log(nin the cases of heapsort and quicksortwhere the are appropriate coefficients these formulas merely provide rough measure of performance as functions of nand they allow the classification of sorting algorithms into primitivestraight methods ( and advanced or "logarithmicmethods ( *log( )for practical purposeshoweverit is helpful to have some experimental data available that shed light on the coefficients which further distinguish the various methods moreoverthe formulas do not take into account the computational effort expended on operations other than key comparisons and item movessuch as loop controletc clearlythese factors depend to some degree on individual systemsbut an example of experimentally obtained data is nevertheless informative table shows the times (in secondsconsumed by the sorting methods previously discussedas executed by the modula- system on lilith personal computer the three columns contain the times used to sort the already ordered arraya random permutationand the inversely ordered array table is for itemstable for items the data clearly separate the methods from the *log(nmethods the following points are noteworthy the improvement of binary insertion over straight insertion is marginal indeedand even negative in the case of an already existing order bubblesort is definitely the worst sorting method among all compared its improved version