This is my attempt at the code but it doesnt work the merge function is found be
ID: 3546644 • Letter: T
Question
This is my attempt at the code but it doesnt work the merge function is found below
/* Return a a copy of array with its items sorted.
Recursively divide the problem into smaller problems and then merge the
sorted lists together using the provided `merge` function.
*/
template <class T>
T *merge_sort(const T *array, int n) {
int mid=0;
if (n == 0)
return NULL;
// TODO: Implement the remainder of this function
if(n>1){
mid=n/2;
merge_sort(array,mid);
merge_sort(array+mid,n);
merge(array,mid,array+mid,n);
// For now this just returns a dummy array of the same size.
// T *tmp = new T[n];
//while (n > 0)
// tmp[--n] = array[0];
//return tmp;
}
}
////////////////Merge///////////
/* Given a sorted deallocatable array `left` with `left_n` elements, and a
sorted deallocatable array `right` with `right_n` elements, return a new
sorted deallocatable array that contains all the elements of `left` and
`right`.
The `left` and `right` arrays must be deallocatable because they are
deallocated as part of this function.
*/
template <class T>
T *merge(T *left, int left_n, T *right, int right_n) {
int n = left_n + right_n;
if (counts.find(n) != counts.end())
counts[n] += 1;
else
counts[n] = 1;
int idx = 0, left_idx = 0, right_idx = 0;
T *retval = new T[n];
while (left_idx < left_n || right_idx < right_n) {
if (left_idx < left_n && right_idx < right_n) { // Choose the smaller
if (left[left_idx] <= right[right_idx])
retval[idx++] = left[left_idx++];
else
retval[idx++] = right[right_idx++];
}
else if (left_idx < left_n) // No more on the right
retval[idx++] = left[left_idx++];
else // No more on the left
retval[idx++] = right[right_idx++];
}
delete [] left;
delete [] right;
return retval;
}
Explanation / Answer
void merge(int a[], int low, int mid, int high) { int b[10000]; int i = low, j = mid + 1, k = 0; while (i <= mid && j <= high) { if (a[i] <= a[j]) b[k++] = a[i++]; else b[k++] = a[j++]; } while (i <= mid) b[k++] = a[i++]; while (j <= high) b[k++] = a[j++]; k--; while (k >= 0) { a[low + k] = b[k]; k--; } } void mergesort(int a[], int low, int high) { if (low < high) { int m = (high + low)/2; mergesort(a, low, m); mergesort(a, m + 1, high); merge(a, low, m, high); } } void merge(int a[], int low, int mid, int high) { int b[10000]; int i = low, j = mid + 1, k = 0; while (i <= mid && j <= high) { if (a[i] <= a[j]) b[k++] = a[i++]; else b[k++] = a[j++]; } while (i <= mid) b[k++] = a[i++]; while (j <= high) b[k++] = a[j++]; k--; while (k >= 0) { a[low + k] = b[k]; k--; } } void mergesort(int a[], int low, int high) { if (low < high) { int m = (high + low)/2; mergesort(a, low, m); mergesort(a, m + 1, high); merge(a, low, m, high); } }Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.