/*********** * in_class_merge.c * * Re-written during Nate's tutorial, based on his work in merge.c. * * Changes include : * - all function calls take a pointer to the start of an array and its length * - temporary space is declared once, outside of any function * - printing of all parameters to each function call * - compilation and output placed here in the header. * * Running it looks like this : * * $ make in_class_merge * cc in_class_merge.c -o in_class_merge * $ ./in_class_merge * main - initial array : [1 4 3 3 2 ] * * sort(0x7ffeecbd92c0, 5) * input array: [1 4 3 3 2 ] * left array: [1 4 ] * right array: [3 3 2 ] * * sort(0x7ffeecbd92c0, 2) * input array: [1 4 ] * left array: [1 ] * right array: [4 ] * * sort(0x7ffeecbd92c0, 1) * input array: [1 ] * size <= 1 * * sort(0x7ffeecbd92c4, 1) * input array: [4 ] * size <= 1 * * merge(0x7ffeecbd92c0, 1, 0x7ffeecbd92c4, 1, 0x7ffeecbd92c0, 2) * left = [1 ] * right = [4 ] * destination = [1 4 ] * * sort(0x7ffeecbd92c8, 3) * input array: [3 3 2 ] * left array: [3 ] * right array: [3 2 ] * * sort(0x7ffeecbd92c8, 1) * input array: [3 ] * size <= 1 * * sort(0x7ffeecbd92cc, 2) * input array: [3 2 ] * left array: [3 ] * right array: [2 ] * * sort(0x7ffeecbd92cc, 1) * input array: [3 ] * size <= 1 * * sort(0x7ffeecbd92d0, 1) * input array: [2 ] * size <= 1 * * merge(0x7ffeecbd92cc, 1, 0x7ffeecbd92d0, 1, 0x7ffeecbd92cc, 2) * left = [3 ] * right = [2 ] * destination = [2 3 ] * * merge(0x7ffeecbd92c8, 1, 0x7ffeecbd92cc, 2, 0x7ffeecbd92c8, 3) * left = [3 ] * right = [2 3 ] * destination = [2 3 3 ] * * merge(0x7ffeecbd92c0, 2, 0x7ffeecbd92c8, 3, 0x7ffeecbd92c0, 5) * left = [1 4 ] * right = [2 3 3 ] * destination = [1 2 3 3 4 ] * * main - sorted array : [1 2 3 3 4 ] * * Jim Mahoney | March 29 2018 ***********/ #include <stdio.h> #include <stdlib.h> #define half_max_size 10000 int temp1[half_max_size]; int temp2[half_max_size]; void printArray(int* array, int size){ // print array[0] through array[size-1] e.g. "[10 11 12 ]" int i; printf("["); for(i=0; i<size; i++){ printf("%d ", array[i]); } printf("]\n"); }; void merge(int* left_array, int left_size, int* right_array, int right_size, int* destination_array, int destination_size){ // merge two already-sorted arrays left & right into the destination array, // using temp1 and temp2 buffers as temporary space. // It's OK if destination overlaps left and/or right in memory. int i, j, k; // (left, right, destination) indices. printf(" merge(%p, %i, %p, %i, %p, %i) \n", left_array, left_size, right_array, right_size, destination_array, destination_size); printf(" left = "); printArray(left_array, left_size); printf(" right = "); printArray(right_array, right_size); // copy left and right to temporary storage for (i=0; i<left_size; i++){ temp1[i] = left_array[i]; } for (j=0; j<right_size; j++){ temp2[j] = right_array[j]; }; i = j = k = 0; // move smallest item from either left or right to destination. while(i < left_size && j < right_size){ if (temp1[i] <= temp2[j]){ destination_array[k] = temp1[i]; i++; } else { destination_array[k] = temp2[j]; j++; }; k++; }; // move remaining elements in left or right. while(i < left_size){ destination_array[k] = temp1[i]; i++; k++; }; while(j < right_size){ destination_array[k] = temp2[j]; j++; k++; }; printf(" destination = "); printArray(destination_array, destination_size); printf("\n"); }; void sort(int* array, int size){ // sort in place [array[0] ... array[size-1]] int left_size, right_size; int *left_array, *right_array; printf(" sort(%p, %i)\n", array, size); printf(" input array: "); printArray(array, size); if (size > 1){ left_size = size / 2; left_array = array; printf(" left array: "); printArray(left_array, left_size); right_size = size - left_size; right_array = array + left_size; // <== pointer arithmetic ! printf(" right array: "); printArray(right_array, right_size); printf("\n"); sort(left_array, left_size); sort(right_array, right_size); merge(left_array, left_size, right_array, right_size, array, size); } else { printf(" size <= 1\n\n"); } }; int main(){ int size = 5; int array[] = {1, 4, 3, 3, 2}; printf("main - initial array : "); printArray(array, size); printf("\n"); sort(array, size); printf("main - sorted array : "); printArray(array, size); printf("\n"); return 0; };