USA: +1 (725) 712-1730 
Sign in
Textbook: Introduction to Algorithms (3rd edition) by T. Cormen, C. Leiserson, R. Rivest and C. Stein, MIT Press, 2009
Show all work.
Figure 2.4 from textbook:
1. a) Using Figure 2.4 in CLRS as a model, illustrate the operation of merge sort on the array A (3,51, 15, 9,36, 56,49,2) Solution. Your solution here. b) Prove that olg(n)) nw(g(n)) is the empty set Solution. Your solution here.
Expert Answer
/* The task is to complete merge() which is used
in below mergeSort() */
/* l is for left index and r is right index of the
sub-array of arr to be sorted
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l+(r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
} */
// Merges two subarrays of arr[]. First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
// Your code here
int j,k,i;
int n1=m-l+1;
int n2=r-m;
int l1[n1],r1[n2];
for(i=0;i<n1;i++)
{
l1[i]=arr[l+i];
}
for(j=0;j<n2;j++)
{
r1[j]=arr[m+1+j];
}
j=0;
k=l;
i=0;
while(i<n1 && j<n2)
{
if(l1[i]<=r1[j])
{
arr[k]=l1[i];
k=k+1;
i=i+1;
}
else
{
arr[k]=r1[j];
k=k+1;
j=j+1;
}
}
while(i<n1)
{
arr[k]=l1[i];
k=k+1;
i=i+1;
}
while(j<n2)
{
arr[k]=r1[j];
k=k+1;
j=j+1;
}
}
