Question

#1. There is an error in the code. Not a grave error – the sort still works correctly. What is the
error?
( no code needs to be added or deleted to correct the error )
#2. The algorithm can be improved in terms of memory use. How? ( no new code is necessary )
# 3. What do lines 26-27 do ? ( copying arryptr into temp is not the complete answer. Be
specific )
#4.What do lines 30-31 do ? (copying arryptr into temp is not the complete answer. Be
specific )
#5. Draw a tree diagram ( as above ) illustrating the order of calls ( along with the mid ) for the
array
77 44 99 11 -666 22 55 -23

mergesortcode

template
void mergesort(T* arrayptr, const int& arraySize )
{
sortmerge( arrayptr, arraySize, 0, arraySize − 1 );
}

template
void sortmerge( T *arrayptr, int arraySize, int l, int r )
{

int mid, i, j, k;

T* temp = new T[ arraySize ];

if ( l < r )
{
mid = (r + l)/2;

sortmerge( arrayptr, arraySize, l, mid );
sortmerge( arrayptr, arraySize, mid + 1, r );


for ( i = mid + 1; i > l; i−− )
temp[ i − 1 ]= arrayptr[ i − 1 ];

for ( j = mid; j < r; j++ )
temp[ r + mid − j ] = arrayptr[ j + 1 ];

for ( k = l; k <= r; k++)
arrayptr[k] = ( temp[i] < temp[j] ) ? temp[i++] : temp[j−−];

temp = 0;
delete [] temp;
}

Answer 1

So I have put the code which I use for MergeSort. You can try using this if you want.

#include <stdio.h>
#include <conio.h>
#define size 100
void merge(int a[], int, int, int);
void merge_sort(int a[],int, int);
void main()
{
int arr[size], i, n;
printf("\n Enter the number of elements in the array : ");
scanf("%d", &n);
printf("\n Enter the elements of the array: ");
for(i=0;i<n;i++)
{
scanf("%d", &arr[i]);
}
merge_sort(arr, 0, n-1);
printf("\n The sorted array is: \n");
for(i=0;i<n;i++)
printf(" %d\t", arr[i]);
getch();
}
void merge(int arr[], int beg, int mid, int end)
{
int i=beg, j=mid+1, index=beg, temp[size], k;
while((i<=mid) && (j<=end))
{
if(arr[i] < arr[j])
{
temp[index] = arr[i];
i++;
}
else
{
temp[index] = arr[j];
j++;
}
index++;
}
if(i>mid)
{
while(j<=end)
{

  temp[index] = arr[j];
j++;
index++;
}
}
else
{
while(i<=mid)
{
temp[index] = arr[i];
i++;
index++;
}
}
for(k=beg;k<index;k++)
arr[k] = temp[k];
}
void merge_sort(int arr[], int beg, int end)
{
int mid;
if(beg<end)
{
mid = (beg+end)/2;
merge_sort(arr, beg, mid);
merge_sort(arr, mid+1, end);
merge(arr, beg, mid, end);
}
}

1.) For the error, from what I could infer, there is a curly bracket missing. But if you are saying that your code is working then I do not think that is the error.

2.) For improving the code in terms of memory use, you are using a lot of for loops and for each iteration in each loop it will occupy more memory. Thus find a way to reduce the number of for loops. Maybe go through my code for reference.

3.) The code in lines 26-27 is just merging your arrays. For merge sort, we divide the given array in 2 halves and recursively sort it and then we need to merge it.

4.) The code in lines 30-31 is checking whether the elements are sorted in the array or not. Accordingly the value is incremented.