possiblewithout testing whether the new cell can be inserted this would place the new cell in leaf and probably violate the heap orderto fix the heap orderpercolate the new cell up in the normal manner write routine to include this ideaand compare the running time with standard implementation of heapsort propose an algorithm to sort large file using only two tapes show that lower bound of !/ on the number of heaps is implied by the fact that buildheap uses at most comparisons use stirling' formula to expand this bound is an -by- matrix in which the entries in each rows are in increasing order and the entries in each column are in increasing order (reading top to bottomconsider the problem of determining if is in using three-way comparisons ( one comparison of with [ ][jtells you either that is less thanequal toor greater than [ ][ ] give an algorithm that uses at most comparisons prove that any algorithm must use at least comparisons there is prize hidden in boxthe value of the prize is positive integer between and nand you are given to win the prizeyou have to guess its value your goal is to do it in as few guesses as possiblehoweveramong those guessesyou may only make at most guesses that are too high the value will be specified at the start of the gameand if you make more than guesses that are too highyou lose sofor exampleif you then can win in guesses by simply guessing the sequence suppose log nwhat strategy minimizes the number of guessesb suppose show that you can always win in / guesses suppose show that any algorithm that wins the prize must use / guesses give an algorithm and matching lower bound for any constant references knuth' book [ is comprehensive reference for sorting gonnet and baeza-yates [ has some more resultsas well as huge bibliography the original paper detailing shellsort is [ the paper by hibbard [ suggested the use of the increments and tightened the code by avoiding swaps theorem is from [ pratt' lower boundwhich uses more complex method than that suggested in the textcan be found in [ improved increment sequences and upper bounds appear in [ ][ ]and [ ]matching lower bounds have been shown in [ it has been shown that no increment sequence gives an ( log nworst-case running time [ the average-case running time for shellsort is still unresolved yao [ has performed an extremely complex analysis for the three-increment case the result has yet to be extended to more incrementsbut has been slightly improved [ the paper by jiangliand vityani [ has shown an ( + / lower bound on the average-case running time of -pass shellsort experiments with various increment sequences appear in [