Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* C program for Merge Sort */
- #include<stdlib.h>
- #include<stdio.h>
- #define infinite 9999; //Used for sentinels
- void MERGE(A, p, q, r);
- void printArray(Arr, size);
- void MERGE_SORT(A, p, r);
- int main(void)
- {
- int A[] = { 12, 11, 13, 5, 6, 7, 2, 9 };
- int arr_size = sizeof(A) / sizeof(A[0]);
- MERGE_SORT(A, 1, arr_size);
- printf("nSorted array is n");
- printArray(A, arr_size);
- return 0;
- }
- void MERGE(int A[], int p, int q, int r)
- {
- int i = 0;
- int j =0;
- int n1 = q - p + 1; //Computing length of sub-array 1
- int n2 = r - q; //Computing length of sub-array 2
- int L[n1]; //Creating Left array
- int R[n2]; //Creating Right array
- for (int i = 1; i < n1; i++) {
- L[i] = A[p + i - 1];
- }
- for (int j = 1; j < n2; j++) {
- L[j] = A[q + j];
- }
- L[n1] = 99; //Placing Ssentinel at the end of array
- R[n2] = 99;
- i = 1;
- j = 1;
- /*Prior to the first iteration k = p, so the subarray is empty.
- Both L[i] and R[j] are the smallest elements of their arrays and have not
- been copied back to A*/
- for (int k = p; k < r; k++) {
- if (L[i] <= R[j]) {
- A[k] = L[i];
- i++;
- }
- else if (A[k] = L[i])
- j++;
- }
- }
- void MERGE_SORT(int A[], int p, int r)
- {
- //During first iteration p = 1 & r = 8
- if (p < r) {
- int q = (p + r) / 2;
- MERGE_SORT(A, p, q);
- MERGE_SORT(A, q + 1, r);
- MERGE(A, p, q, r);
- }
- }
- int *L = malloc(n1 * sizeof(*L));
- if (L == NULL) {
- // handle error
- }
Add Comment
Please, Sign In to add comment