Fill in the merge method to merge two sorted arrays into one larger sorted array, which is the key step to combine recursive problems in merge sort. Click here to watch a video I made on merge sort if you'd like some help with this step. You can also watch a cute video here on a dance for merge sort.
Student Code
#include <stdio.h>
#include <cstring>
/**
* @brief Print the elements in an array, separated by spaces
*
* @param x Array to print
* @param N Length of array
*/
void printArray(float* x, int N) {
for (int i = 0; i < N; i++) {
printf("%g ", x[i]);
}
printf("\n");
}
/**
* @brief Merge the sorted elements in A and the sorted elements into B
* into one full sorted list in the array y
*
* @param A First sorted array
* @param M Length of first sorted array
* @param B Second sorted array
* @param N Length of second sorted array
* @param y Staging area, assumed to have length at least M+N.
The merged solution should go here
*/
void merge(float* A, int M, float* B, int N, float* y) {
// TODO: Fill this in
}
/**
* @brief A recursive helper function for merge sort
*
* @param x The array to sort
* @param N Length of the array
* @param y Staging area, which is assumed to have length at least N
*/
void mergeSortRec(float* x, int N, float* y) {
if (N > 1) {
int mid = N/2;
float* A = x;
float* B = A+mid;
mergeSortRec(A, mid, y);
mergeSortRec(B, N-mid, y);
merge(A, mid, B, N-mid, y);
memcpy(x, y, N*sizeof(float));
}
}
/**
* @brief Entry point for sorting an array with merge sort.
* By the end of this method, the elements in x will be sorted
*
* @param x Array to sort
* @param N Length of array
*/
void mergeSort(float* x, int N) {
float* y = new float[N]; // Staging area
mergeSortRec(x, N, y);
delete[] y;
}
Click compile to compile your code. If it succeeds with no syntax errors, then click run to run your code. If it passes the tests, it will automatically submit to Canvas and send you an e-mail. You must be connected to the Ursinus Network for submission to be successful! You will receive a copy of your code via e-mail, so you'll know that it was submitted if you receive that e-mail! Please Enter your Ursinus netid before clicking run. This is not your ID number or your email. For example, my netid is ctralie (non Ursinus students can simply enter their name to get this to run, but they won't get an e-mail record or any form of credit)