C Program For Merge Sort Algorithm in Data Structure
Learn How To Sort Two Integer Arrays using Merge Sort Algorithm in C Programming Language. It is important that we should know about How A For Loop Works before getting further with the C Program Code. The merge sort program in C language takes in two arrays as input, sorts them and stores it in the third array.
What is Merge Sort Algorithm?
Merge Sort Technique was designed by Jon Von Neumann in 1945. The objective of this algorithm is to merge Two already Sorted Lists and combine them in a Single Sorted List. The Merge Sort Algorithm works on Divide and Conquer Algorithm where a given problem is divided into smaller subdivisions.
One element from each of the arrays is taken and compared. The element that is the smaller is copied into the third array. This process is continued till the elements of one array gets copied into the third array. Later, the remaining elements of the array are copied into the third array.
Note: The first and second arrays should consist of sorted elements. If the elements are not in sorted order, then the merge sort in c will not work.
There are two types of Merge Sort techniques:
- Top Down Merge Sort
- Bottom Up Merge Sort
Merge Sort Example
Array 1: 10 20 30 40 50
Array 2: 60 70 80 90 100 120 140
Sorted Array: 10 20 30 40 50 60 70 80 90 100 120 140
Merge Sort Algorithm Analysis
Merge Sort is a Stable Sort. Merge Sorting Algorithm is also not an In-Place Sort. It requires O(n) Extra Space. In every pass, there will be merging of n Elements and therefore the performance of the Algorithm is O(n log2n). It has O(n log n) performance in both Worst Case Scenario and Average Case Scenario.
C Program To Sort Two Arrays using Merge Sort Algorithm
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 | #include<stdio.h> int main() { int first[30], second[30], third[30]; int limit_1, limit_2; int i, j, k; printf("\nEnter Limit For First Array:\t"); scanf("%d", &limit_1); printf("\nEnter the Elements of Array 1:\n"); for(i = 0; i < limit_1; i++) { scanf("%d", &first[i]); } printf("\nEnter Limit For Second Array:\t"); scanf("%d", &limit_2); printf("\nEnter the Elements of Array 2:\n"); for(j = 0; j < limit_2; j++) { scanf("%d", &second[j]); } i = 0; j = 0; k = 0; while((i < limit_1) && (j < limit_2)) { if(first[i] > second[j]) { third[k++] = second[j++]; } else { third[k++] = first[i++]; } } while(i < limit_1) { third[k++] = first[i++]; } while(j < limit_2) { third[k++] = second[j++]; } printf("\nArray 1:\n"); for(i = 0; i < limit_1; i++) { printf("%d\t", first[i]); } printf("\nArray 2:\n"); for(i = 0; i < limit_2; i++) { printf("%d\t", second[i]); } printf("\nArray 3:\n"); for(i = 0; i < limit_1 + limit_2; i++) { printf("%d\t", third[i]); } printf("\n"); return 0; } |
Output
If you have any compilation errors or doubts in this code to sort array using Merge Sort C Program in Data Structure, let us know about in the comment section below.
The merge sort in c programming algorithm is quite easy actually. I was confused on comparison of elements. Nice code.
There are a fee disadvantages with Merge Sorting algorithm.
1. This algorithm makes too many recursive attempts.
2. It is an in-place sorting algorithm that needs 0(n) extra memory for sorting the elements.