/** * Mergesort.c * Sort the inputted integers, using merge-sort algorithm. **/ #include #include /** * merge() * Merge two sorted arrays, A with a integers and * B with b integers, into a sorted array C. **/ void merge (int *A, int a, int *B, int b, int *C) { int i,j,k; i = 0; j = 0; k = 0; while (i < a && j < b) { if (A[i] <= B[j]) { /* copy A[i] to C[k] and move the pointer i and k forward */ C[k] = A[i]; i++; k++; } else { /* copy B[j] to C[k] and move the pointer j and k forward */ C[k] = B[j]; j++; k++; } } /* move the remaining elements in A into C */ while (i < a) { C[k]= A[i]; i++; k++; } /* move the remaining elements in B into C */ while (j < b) { C[k]= B[j]; j++; k++; } } /** * merge_sort() * Sort array A with n integers, using merge-sort algorithm. **/ void merge_sort(int *A, int n) { int i; int *A1, *A2; int n1, n2; if (n < 2) return; /* the array is sorted when n=1.*/ /* divide A into two array A1 and A2 */ n1 = n / 2; /* the number of elements in A1 */ n2 = n - n1; /* the number of elements in A2 */ A1 = (int*)malloc(sizeof(int) * n1); A2 = (int*)malloc(sizeof(int) * n2); /* move the first n/2 elements to A1 */ for (i =0; i < n1; i++) { A1[i] = A[i]; } /* move the rest to A2 */ for (i = 0; i < n2; i++) { A2[i] = A[i+n1]; } /* recursive call */ merge_sort(A1, n1); merge_sort(A2, n2); /* conquer */ merge(A1, n1, A2, n2, A); free(A1); free(A2); } /** * main() * The main function for input and output **/ void main(int argv, char** args) { int i, n; int *A; char c; printf("Please input the number of elements: " ); scanf("%d", &n); A = (int *)malloc(sizeof(int) * n); printf("Please input %d integers: ", n); for (i = 0; i < n; i++) { scanf("%d", &(A[i])); } /* print the original array */ printf("************** Result **************\n"); printf("The input array is: "); for (i = 0; i < n; i++) { printf("%d ", A[i]); } printf("\n"); /* merge sort A */ merge_sort(A, n); /* print the sorted array */ printf("The sorted array is: "); for (i = 0; i < n; i++) { printf("%d ", A[i]); } printf("\n"); free(A); printf("Press ENTER to return."); c = _getch(); }