We can modify Insertion Sort to insert a pair of elements at a time, instead of only one element Find the larger element of the pair and put it into its proper location in the sorted array using linear search (as in standard insertion sort). Then, starting from where the larger element ended up, put the smaller element into its proper location again using linear search (a) Write the pseudo code, using a sentinel, for this algorithm. You may assume that the size of the array is even. (b) Assume the size of the array n 4 i. What is the best-case number of comparisons? Just state the number and show your ii. What is the worst-case number of comparisons? Just state the number and show your iii. What is the average-case number of comparisons? Justify. HINT: There are 24 pos- input. Otherwise, no justification needed. input. Otherwise, no justification needed. sible orderings, which is a lot. The calculation is more manageable if you realize that (c) Calculate the average case number of comparisons for general n, where n is even. Show (d) How does the average case number of comparisons compare with the average case of the first pair of elements essentially defines the whole ordering your work. standard insertion sort? We can modify Insertion Sort to insert a pair of elements at a time, instead of only one element Find the larger element of the pair and put it into its proper location in the sorted array using linear search (as in standard insertion sort). Then, starting from where the larger element ended up, put the smaller element into its proper location again using linear search (a) Write the pseudo code, using a sentinel, for this algorithm. You may assume that the size of the array is even. (b) Assume the size of the array n 4 i. What is the best-case number of comparisons? Just state the number and show your ii. What is the worst-case number of comparisons? Just state the number and show your iii. What is the average-case number of comparisons? Justify. HINT: There are 24 pos- input. Otherwise, no justification needed. input. Otherwise, no justification needed. sible orderings, which is a lot. The calculation is more manageable if you realize that (c) Calculate the average case number of comparisons for general n, where n is even. Show (d) How does the average case number of comparisons compare with the average case of the first pair of elements essentially defines the whole ordering your work. standard insertion sort
