sorting the performance of shellsort is quite acceptable in practiceeven for in the tens of thousands the simplicity of the code makes it the algorithm of choice for sorting up to moderately large input heapsort as mentioned in priority queues can be used to sort in ( log ntime the algorithm based on this idea is known as heapsort and gives the best big-oh running time we have seen so far recall from that the basic strategy is to build binary heap of elements this stage takes (ntime we then perform deletemin operations the elements leave the heap smallest firstin sorted order by recording these elements in second array and then copying the array backwe sort elements since each deletemin takes (log ntimethe total running time is ( log nthe main problem with this algorithm is that it uses an extra array thusthe memory requirement is doubled this could be problem in some instances notice that the extra time spent copying the second array back to the first is only ( )so that this is not likely to affect the running time significantly the problem is space clever way to avoid using second array makes use of the fact that after each deleteminthe heap shrinks by thus the cell that was last in the heap can be used to store the element that was just deleted as an examplesuppose we have heap with six elements the first deletemin produces now the heap has only five elementsso we can place in position the next deletemin produces since the heap will now only have four elementswe can place in position using this strategyafter the last deletemin the array will contain the elements in decreasing sorted order if we want the elements in the more typical increasing sorted orderwe can change the ordering property so that the parent has larger element than the child thuswe have (max)heap in our implementationwe will use (max)heap but avoid the actual adt for the purposes of speed as usualeverything is done in an array the first step builds the heap in linear time we then perform deletemaxes by swapping the last element in the heap with the firstdecrementing the heap sizeand percolating down when the algorithm terminatesthe array contains the elements in sorted order for instanceconsider the input sequence the resulting heap is shown in figure figure shows the heap that results after the first deletemax as the figures implythe last element in the heap is has been placed in part of the heap array that is technically no longer part of the heap after more deletemax operationsthe heap will actually have only one elementbut the elements left in the heap array will be in sorted order the code to perform heapsort is given in figure the slight complication is thatunlike the binary heapwhere the data begin at array index the array for heapsort contains data in position thus the code is little different from the binary heap code the changes are minor