In this tutorial, you will learn about the Merge Sort and how to implement in C Program.
Merge Sort Algorithm:
Merge Sort is a sorting algorithm that follows a Divide and Conquer algorithm approach to sort the elements in an array in ascending or descending order.
It divides the array into two halves and sorts them separately. Again the two halves are divided into separate two halves and the process keeps on going until the elements are totally separated. After that, the elements are combined together in the same steps as they were separated but while combining the elements are sorted in each steps.
When the combining step is completed we will get a fully sorted array.
Time Complexity of Merge Sort:
- Best case:
0(n log n) - Average case:
0(n log n) - Worst case:
0(n log n)
C Program for Merge Sort
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 | //merge sort c program #include <stdio.h> #include <stdlib.h> void MergeSorted(int[], int); void Merg(int[], int[], int, int, int); void MSort(int[], int[], int, int); int main() { int i, numElemt, arr[50]; //User Input printf("Enter the number of elements you want to sort for: "); scanf("%d", &numElemt); printf("Enter %d elements\n", numElemt); for (i = 0; i < numElemt; i++) { scanf("%d", &arr[i]); } MergeSorted(arr, numElemt); printf("After Merge Sort, the elements are: "); for (i = 0; i < numElemt; i++) { printf("%d ", arr[i]); } printf("\n"); } void Merge(int arr[], int temp[], int lpos, int rpos, int rend) { int i, lend, numElemt, temppos; lend = rpos - 1; temppos = lpos; numElemt = rend - lpos + 1; while (lpos <= lend && rpos <= rend) { if (arr[lpos] <= arr[rpos]) temp[temppos++] = arr[lpos++]; else temp[temppos++] = arr[rpos++]; } while (lpos <= lend) temp[temppos++] = arr[lpos++]; while (rpos <= rend) temp[temppos++] = arr[rpos++]; for (i = 0; i < numElemt; i++, rend--) arr[rend] = temp[rend]; } void MSort(int arr[], int temp[], int left, int right) { int mid; if (left < right) { mid = (left + right) / 2; MSort(arr, temp, left, mid); MSort(arr, temp, mid + 1, right); Merge(arr, temp, left, mid + 1, right); } } void MergeSorted(int arr[], int numElemt) { int *temparray; temparray = malloc(sizeof(int) *numElemt); MSort(arr, temparray, 0, numElemt - 1); free(temparray); } |
The output of merge sort in C program.
