Question
C programming Merge sort #include int b[100]; // temporary array used for merging void DoMerging(int a[], int startIndex, int midIndex, int endIndex) { // Here
C programming Merge sort
#include
int b[100]; // temporary array used for merging
void DoMerging(int a[], int startIndex, int midIndex, int endIndex) {
// Here we should merge the subllists a[startIndex] to a[midIndex] with
// a[midIndex+1] to a[endIndex] together into b[], in ascending order
// Please consult lecture notes for an example of how the merge is done!
// Please use b[] as temporary array for merging!
// INSERT CODE HERE
// copy the result from b[] back to a[]
int k;
printf("Merge Result: ");
for(k = startIndex; k <= endIndex; k++){
a[k] = b[k];
printf("%d ", b[k]);
}
printf(" ");
}
void MergeSort(int a[], int startIndex, int endIndex) {
// this is the recursive function for MergeSort
// we separate the list into two sublists and call mergesort again;
// the sublist is marked by startIndex and endIndex
int midIndex;
if(startIndex < endIndex) {
// more than one element, pls sort!
midIndex = (startIndex + endIndex) / 2;
MergeSort(a, startIndex, midIndex);
MergeSort(a, midIndex+1, endIndex);
DoMerging(a, startIndex, midIndex, endIndex);
} else {
// only one element, no need to sort!
return;
}
}
int main() {
int i;
int a[] = { 17, 22, 10, 22, 49, 30, 25, 2 };
printf("Original: ");
for(i = 0; i < 8; i++)
printf("%d ", a[i]);
printf(" ");
MergeSort(a, 0, 7); // in the beginning, we put in the whole list, which is from
// 0 to 7
printf("Final Result: ");
for(i = 0; i < 8; i++)
printf("%d ", a[i]);
printf(" ");
}
A successful output should look like this:
Original: 17 22 10 22 49 30 25 2 Merge Result: 17 22 Merge Result: 10 22 Merge Result: 10 17 22 22 Merge Result: 30 49 Merge Result: 2 25 Merge Result: 2 25 30 49 Merge Result: 2 10 17 22 22 25 30 49 Final Result: 2 10 17 22 22 25 30 49 |
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started