elements in heap array output next element read end of run rebuild heap end of run end of tape [ [ [ run run run rebuild heap figure example of run construction summary sorting is one of the oldest and most well-studied problems in computing for most general internal sorting applicationsan insertion sortshellsortmergesortor quicksort is the method of choice the decision regarding which to use depends on the size of the input and on the underlying environment insertion sort is appropriate for very small amounts of input shellsort is good choice for sorting moderate amounts of input with proper increment sequenceit gives excellent performance and uses only few lines of code mergesort has ( log nworst-case performance but requires additional space howeverthe number of comparisons that are used is nearly optimalbecause any algorithm that sorts by using only element comparisons must use at least log ( !)comparisons for some input sequence quicksort does not by itself provide this worst-case guarantee and is tricky to code howeverit has almost certain ( log nperformance and can be combined with heapsort to give an ( log nworst-case guarantee strings can be sorted in linear time using radix sortand this may be practical alternative to comparison-based sorts in some instances exercises sort the sequence using insertion sort what is the running time of insertion sort if all elements are equal