notes the hk form geometric seriesthe sum of all hk with is in (htonthus (nnsorting steps are needed for this part where now let when the sequence is arranged as an array with hk columns there are /hk elements in each column thuso(( /hk) sorting steps are needed to sort each columnsince insertion sort has quadratic complexity there are hk columnstherefore the number of sorting steps for hksorting the entire data sequence is in (( /hk) hko(nn/hkagainthe /hk form geometric series whose sum is in ( /htonthereforeagain (nnsteps are needed for this part where it can be shown that for this -sequence the upper bound is tight but there is another -sequence that leads to more efficient behavior of shellsort theoremwith the -sequence qshellsort needs (nlog( ) steps for sorting sequence of length (pratt [pra ]proofif and then (gh( - )( - in , -sorted sequence to the right of each element only the next element can be smaller thereforeo(nsorting steps suffice to sort the sequence with insertion sort considering elements with odd and with even index separatelyit becomes clear that again (nsorting steps suffice to make , -sorted sequence -sorted similarlyo(nsorting steps suffice to make , -sorted sequence -sorted and so on the above -sequence has the property that for each hk also hk and hk occursso (nsorting steps suffice for each hk altogether there are log( ) elements in the -sequencethus the complexity of shellsort with this -sequence is in (nlog( ) the -sequence of pratt performs best asymptoticallybut it consists of log( ) elements particularlyif the data sequence is presorteda -sequence with less elements is bettersince the data sequence has to be scanned (by the for- -loop in the programfor each hkeven if only few sorting steps are performed by combining the arguments of these two theorems -sequences with (log( )elements can be derived that lead to very good performance in practiceas for instance the -sequence of the program but unfortunatelythere seems to be no -sequence that gives shellsort worst case performance of (nlog( )it is an open question whether possibly the average complexity is in (nlog( ) heap sort heapsort is sorting technique which sorts contiguous list of length with (nlog (ncomparisons and movement of entrieseven in the worst case hence it achieves worst-case bounds better than those of quicksortand for contiguous list it is better than mergesortsince it needs only small and constant amount of space apart from the list being sorted heapsort proceeds in two phases firstall the entries in the list are arranged to satisfy heap propertyand then top of the heap is removed and another entry is promoted to take its place repeatedly therefore we need procedure which builds an initial heap to arrange all the entries in the list to satisfy heap property the procedure which builds an initial heap uses procedure which adjust the ith entry in the list whose entries at and positions already satisfy heap property in such manner entry at ith position in the list will also satisfy heap property the following code implements the algorithm void adjust(list xint iint nint jkboolean flag lovely professional university