Merge Sort Program Implementation in C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include<stdio.h> #include<conio.h> // successfully compiled in turbo c // this function merges the splitted array, l = left, r= right, m=mid void merge(int arr[], int l, int m, int r) { int i = 0, j = 0, k = 0; // three int variables for 'left', 'right' and 'arr' array int n1 = m - l + 1; // n1 and n2 contains the total numbers in 'left' and 'right' array int n2 = r - m; int left[10], right[10]; // two auxiliary arrays to store numbers // store elements from l to m in 'left' array for (i = 0; i < n1; i++) { left[i] = arr[i + l]; } // store elements from m+1 to r in 'right' array for (j = 0; j < n2; j++) { right[j] = arr[j + m + 1]; } // reset i and j for auxiliary array i = 0; j = 0; // set k to l, as 'arr' will start from l k = l; // copy 'left' and 'right' arrays to 'arr' while (i < n1 && j < n2) { if (left[i] < right[j]) { arr[k] = left[i]; i++; k++; } else { arr[k] = right[j]; j++; k++; } } // while closed // copy remaining elements from 'left' array (if any) while (i < n1) { arr[k] = left[i]; k++; i++; } // copy remaining elements from 'right' array (if any) while (j < n2) { arr[k] = right[j]; k++; j++; } } // function which splits array into half void split(int arr[], int l, int r) { int m; // return if there is only one element in array (logical) if (l == r) { return; } m = (r + l) / 2; // get the mid of array // split the left and right array until there is only one element left split(arr, l, m); split(arr, m + 1, r); // now call merge function to merge elements splitted earlier merge(arr, l, m, r); } void main() { int i, n, start = 0, arr[10]; clrscr(); printf("Number of elements :"); scanf("%d", &n); for (i = 0; i < n; i++) { printf("\nEnter the number %d :", i + 1); scanf("%d",&arr[i]); } split(arr, start, n); printf("\n"); for (i = 0; i < n; i++) { printf("%d,", arr[i]); } getch(); } |
