againby recalling proposition phase runs in ( timeand henceso does the entire insertion-sort algorithm alternativelywe could change our definition of insertion-sort so that we insert elements starting from the end of the priority-queue list in phase in which case performing insertion-sort on sequence that is already sorted would run in (ntime indeedthe running time of insertion-sort in this case is ( )where is the number of inversions in the sequencethat isthe number of pairs of elements that start out in the input sequence in the wrong relative order heaps the two implementations of the priorityqueuesort scheme presented in the previous section suggest possible way of improving the running time for priorityqueue sorting for one algorithm (selection-sortachieves fast running time for phase but has slow phase whereas the other algorithm (insertion-sorthas slow phase but achieves fast running time for phase if we can somehow balance the running times of the two phaseswe might be able to significantly speed up the overall running time for sorting this isin factexactly what we can achieve using the priority-queue implementation discussed in this section