4 void merge (float *, int, int, int);
6 /* sort the (sub)array v from start to end */
8 void merge_sort (float *v, int start, int end) {
9 int middle; /* the middle of the subarray */
11 /* no elements to sort */
12 if (start == end) return;
14 /* one element; already sorted! */
15 if (start == end - 1) return;
17 /* find the middle of the array, splitting it into two subarrays */
18 middle = (start + end) / 2;
20 /* sort the subarray from start..middle */
21 merge_sort (v, start, middle);
23 /* sort the subarray from middle..end */
24 merge_sort (v, middle, end);
26 /* merge the two sorted halves */
27 merge (v, start, middle, end);
30 /* merge the subarray v[start..middle] with v[middle..end], placing the
33 void merge (float *v, int start, int middle, int end) {
34 int v1_n, v2_n, v1_index, v2_index, i;
36 float *v1 = malloc((middle - start) * sizeof(*v1));
37 float *v2 = malloc((end - middle) * sizeof(*v2));
39 /* number of elements in first subarray */
40 v1_n = middle - start;
42 /* number of elements in second subarray */
45 /* fill v1 and v2 with the elements of the first and second
46 * subarrays, respectively
48 for (i=0; i<v1_n; i++) v1[i] = v[start + i];
49 for (i=0; i<v2_n; i++) v2[i] = v[middle + i];
51 /* v1_index and v2_index will index into v1 and v2, respectively... */
55 /* ... as we pick elements from one or the other to place back
58 for (i=0; (v1_index < v1_n) && (v2_index < v2_n); i++) {
60 /* current v1 element less than current v2 element? */
61 if (v1[v1_index] <= v2[v2_index])
63 /* if so, this element belong as next in v */
64 v[start + i] = v1[v1_index++];
66 /* otherwise, the element from v2 belongs there */
67 v[start + i] = v2[v2_index++];
69 /* clean up; either v1 or v2 may have stuff left in it */
71 for (; v1_index < v1_n; i++) v[start + i] = v1[v1_index++];
72 for (; v2_index < v2_n; i++) v[start + i] = v2[v2_index++];
77 int main(int argc, char **argv) {
81 printf("MergeSort.c\n");
84 f = malloc(len * sizeof(*f));
86 for(i = 0; i < argc - 1; i++) {
87 if (!sscanf(argv[i + 1], "%f", f + i)) { printf("Argument %d invalid, float expected instead of '%s'!\n", i, argv[i + 1]); return 1; }
88 printf(" %f\n", f[i]);
92 printf("Usage: MergeSort <list of numbers>\n");
93 printf("Continuing with default input.\n");
94 f = (void *)malloc(sizeof(*f) * (len = 6));
95 f[0] = 3.3; f[1] = 18.18; f[2] = 5.5; f[3] = 99.99; f[4] = 104.104; f[5] = 2.2;
100 for(i = 0; i < len - 1; i++) {
101 printf(" %f,", f[i]);
104 printf(" %f\n", f[len - 1]);
107 merge_sort(f, 0, len);
110 printf(" sorted array = ");
111 for(i = 0; i < len - 1; i++) {
112 printf(" %f,", f[i]);
115 printf(" %f\n", f[len - 1]);