Consider the Merge-Sort (M-S) algorithm presented in class. Give a permutation of the input list (1,...

 

Transcribed Image Text:

Consider the Merge-Sort (M-S) algorithm presented in class. Give a permutation of the input list (1, 2, 3, 4, 5, 6, 7) that will elicit the best-case performance (as measured in number of comparisons) between elements in the input list. How many comparisons are made? We do NOT count comparisons to sentinels. M-S(A, p, r) 1 2 3 4 5 If p<r q=floor((p+r)/2) M-S(A, p, q) M-S(A, q+1, r) M(A, p, q, r) I Consider the Merge-Sort (M-S) algorithm presented in class. Give a permutation of the input list (1, 2, 3, 4, 5, 6, 7) that will elicit the best-case performance (as measured in number of comparisons) between elements in the input list. How many comparisons are made? We do NOT count comparisons to sentinels. M-S(A, p, r) 1 2 3 4 5 If p<r q=floor((p+r)/2) M-S(A, p, q) M-S(A, q+1, r) M(A, p, q, r) I

Answer rating: 100% (QA)

In the MergeSort algorithm the bestcase scenario occurs when the input list is already sorted In thi... View the full answer