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