|
| 1 | +//**************************************** |
| 2 | +// C++ implementation of merge sort |
| 3 | +// |
| 4 | +// Author: Carlos Abraham Hernandez |
| 5 | +// abraham@abranhe.com |
| 6 | +//**************************************** |
| 7 | + |
| 8 | +#include<stdlib.h> |
| 9 | +#include<stdio.h> |
| 10 | + |
| 11 | +// Merge the two half into a sorted data. |
| 12 | +void merge(int arr[], int l, int m, int r) |
| 13 | +{ |
| 14 | + int i, j, k; |
| 15 | + int n1 = m - l + 1; |
| 16 | + int n2 = r - m; |
| 17 | + |
| 18 | + /* create temp arrays */ |
| 19 | + int L[n1], R[n2]; |
| 20 | + |
| 21 | + /* Copy data to temp arrays L[] and R[] */ |
| 22 | + for (i = 0; i < n1; i++) |
| 23 | + L[i] = arr[l + i]; |
| 24 | + for (j = 0; j < n2; j++) |
| 25 | + R[j] = arr[m + 1+ j]; |
| 26 | + |
| 27 | + /* Merge the temp arrays back into arr[l..r]*/ |
| 28 | + i = 0; // Initial index of first subarray |
| 29 | + j = 0; // Initial index of second subarray |
| 30 | + k = l; // Initial index of merged subarray |
| 31 | + while (i < n1 && j < n2) |
| 32 | + { |
| 33 | + if (L[i] <= R[j]) |
| 34 | + { |
| 35 | + arr[k] = L[i]; |
| 36 | + i++; |
| 37 | + } |
| 38 | + else |
| 39 | + { |
| 40 | + arr[k] = R[j]; |
| 41 | + j++; |
| 42 | + } |
| 43 | + k++; |
| 44 | + } |
| 45 | + |
| 46 | + /* Copy the remaining elements of L[], if there |
| 47 | + are any */ |
| 48 | + while (i < n1) |
| 49 | + { |
| 50 | + arr[k] = L[i]; |
| 51 | + i++; |
| 52 | + k++; |
| 53 | + } |
| 54 | + |
| 55 | + /* Copy the remaining elements of R[], if there |
| 56 | + are any */ |
| 57 | + while (j < n2) |
| 58 | + { |
| 59 | + arr[k] = R[j]; |
| 60 | + j++; |
| 61 | + k++; |
| 62 | + } |
| 63 | +} |
| 64 | + |
| 65 | +/* l is for left index and r is right index of the |
| 66 | + sub-array of arr to be sorted */ |
| 67 | +void mergeSort(int arr[], int l, int r) |
| 68 | +{ |
| 69 | + if (l < r) |
| 70 | + { |
| 71 | + // Same as (l+r)/2, but avoids overflow for |
| 72 | + // large l and h |
| 73 | + int m = l+(r-l)/2; |
| 74 | + |
| 75 | + // Sort first and second halves |
| 76 | + mergeSort(arr, l, m); |
| 77 | + mergeSort(arr, m+1, r); |
| 78 | + |
| 79 | + merge(arr, l, m, r); |
| 80 | + } |
| 81 | +} |
| 82 | + |
| 83 | +/* UTILITY FUNCTIONS */ |
| 84 | +/* Function to print an array */ |
| 85 | +void printArray(int A[], int size) |
| 86 | +{ |
| 87 | + int i; |
| 88 | + for (i=0; i < size; i++) |
| 89 | + printf("%d ", A[i]); |
| 90 | + printf("\n"); |
| 91 | +} |
| 92 | + |
| 93 | +/* Driver program to test above functions */ |
| 94 | +int main() |
| 95 | +{ |
| 96 | + int arr[] = {12, 11, 13, 5, 6, 7}; |
| 97 | + int arr_size = sizeof(arr)/sizeof(arr[0]); |
| 98 | + |
| 99 | + printf("Given array is \n"); |
| 100 | + printArray(arr, arr_size); |
| 101 | + |
| 102 | + mergeSort(arr, 0, arr_size - 1); |
| 103 | + |
| 104 | + printf("\nSorted array is \n"); |
| 105 | + printArray(arr, arr_size); |
| 106 | + return 0; |
| 107 | +} |
0 commit comments