Draw the Mergesort tree for the following array a45 27 20 25

Draw the Merge-sort tree for the following array: a=[45, 27, 20, 25, 26, 12, 40, 28). Only the nodes for the first partition arc show: Note that if you are typing, you do not need to worry about graphical depiction. Just place the nodes at each level in each line, milking it clear which node is parent of which node in the tree. In the example above, you could represent: 45.27, 20, 25126.12.40, 28 rightarrow 12, 20.25, 26.27, 28.40.45 Then place kids in each subsequent level into a single line. (b) Suppose that Quicksort in-place is used to sort the following array where the pivot is always chosen to be the last number in the subarray being considered. A simplified version of the textbook code fragment 12.6 in page 553 is included here. Show the contents of the array right after \"/*** partition step ends ***/\" in each recursive call, in order of execution. For each display show also the contents of parameters a and b (see table that follows). Algorithm quicksortInPlace(int[] S, int a, int b) { if (a>=b) return; // subarray is trivially sorted /*** partition step starts ****/ int left-a; int right-b=1; int pivot-S[b]; while (left

Solution

a).

45 , 27, 20 , 25, 26, 12 , 40 , 28
   / \\
   / \\
45 , 27, 20 , 25 26 , 12 , 40 , 28
/ \\ / \\
/ \\ / \\
45 , 27 20 , 25 26 , 12 40 , 28
/ \\ /\\ /\\ /\\
/ \\ / \\ / \\ / \\
45 27 20 25 26 12 40 28

\\ / \\ / \\    / \\ /
\\ / \\ / \\ / \\ /
27 , 45 20 , 25    12 , 26 28 , 40

\\ / \\ /
\\ / \\ /
\\ / \\ /
20, 25, 27, 45 12, 26, 28, 40

\\ /
\\ /
\\ /
\\ /
   12, 20, 25, 26, 27, 28,40,45

b).   

quicksortInPlace(int[] S,int a,int b){
  
if(a>=b) return;
  
int left=a;
int right=b-1;
int pivot=S[b];
  
while((left<=right) and (S[left]<pivot)) left++;
while((left<=right) and (S[right]>pivot)) right--;
  
if(left<=right){
  
temp=S[left];
S[left]=S[right];
S[right]=temp;
left++; right--;
}
}

S[b]=S[left]; S[left]=pivot;

print(\"a=\"+a);
print(\"b=\"+b);

for(int i=0;i<S.length;i++)
{

print(S[i]);
}

quicksortInPlace(S,a,left-1);
quicksortInPlace(S,left+1,b);

}